Untitled

mail@pastecode.io avatar
unknown
plain_text
10 days ago
2.1 kB
3
Indexable
Never
#include <iostream>
#include <set>
#include <functional>
using namespace std;
struct AbsoluteValueComparator { 
    bool operator()(int a, int b)
    { 
        return abs(a) > abs(b); 
    } 
}; 
set<int,AbsoluteValueComparator> Horizontal[101];
void init()
{
    for(int i=0;i<101;i++) Horizontal[i].clear();
}
 
void add(int mX, int mY)
{
    Horizontal[mX].insert(mY);
    Horizontal[mX+1].insert(-mY);
}
 
void remove(int mX, int mY)
{
    Horizontal[mX].erase(mY);
    Horizontal[mX+1].erase(-mY);
}
 
int numberOfCross(int mID)
{
    int temp_X=mID;
    int temp_Y=0;
    int ans=0;
    auto itr=Horizontal[temp_X].begin();
    if(itr==Horizontal[temp_X].end()) return 0;
    advance(itr,Horizontal[temp_X].size()-1);
    while(itr!=Horizontal[temp_X].end())
    {
         
        if(abs(*itr)<=temp_Y) break;
        temp_Y=abs(*itr);
        if(*itr>0)
        {
            temp_X=temp_X+1;
            itr=Horizontal[temp_X].find(-temp_Y);
        }
        else
        {
            temp_X=temp_X-1;
            itr=Horizontal[temp_X].find(temp_Y);
        }
        itr--;
        ans++;
    }
    return ans;
}
 
int participant(int mX, int mY)
{
    int temp_X=mX;
    int temp_Y=mY;
    auto itr=Horizontal[temp_X].lower_bound(temp_Y);
    if(itr==Horizontal[temp_X].end()) return temp_X;
    while(itr!=Horizontal[temp_X].end())
    {
        if(abs(*itr)>=temp_Y) return temp_X;
        temp_Y=abs(*itr);
        if(*itr>0)
        {
            temp_X=temp_X+1;        
            itr=Horizontal[temp_X].find(-temp_Y);
        }
        else
        {
            temp_X=temp_X-1;
            itr=Horizontal[temp_X].find(temp_Y);
        }
        itr++;
    }
    return temp_X;
}

/* 
25 100
11
1
5 5 7 5
2 4 1
5 5 7 4
2 5 5
5 5 7 6
2 5 3
5 5 7 4
3 4 1
5 5 7 5
4 5 2
13
1
2 1 3
4 1 1
4 1 1
5 3 3 3
3 1 3
2 1 7
5 2 5 2
2 3 5
2 1 9
2 2 2
4 4 1
5 1 3 1
13
1
2 5 2
2 4 9
4 7 0
4 5 1
4 2 0
5 5 7 6
5 10 1 10
2 3 1
2 1 4
5 5 8 6
2 3 5
3 1 4
*/
Leave a Comment