Untitled
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