Untitled
unknown
plain_text
a year ago
1.8 kB
10
Indexable
#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;
}Editor is loading...
Leave a Comment