Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- #include <set>
- #include <cstring>
- #include <map>
- #include <algorithm>
- // APIO '09 P2 - The Siruseri Convention Centre
- #define fi first
- #define se second
- #define INF 0x3f3f3f3f
- using namespace std;
- pair<int,int> com[200005],srt[200005];
- vector<pair<int,int>> unq;
- set<pair<int,int>> s;
- int R[200005][19];
- vector<int> ans;
- bool cmp(pair<int,int> p1,pair<int,int> p2) {
- if (p1.se == p2.se)
- return p1.fi > p2.fi;
- return p1.se < p2.se;
- }
- int MIS(int l,int r) {
- if (l == -1 || r == -1)
- return 0;
- if (l > r)
- return 0;
- int i,cnt;
- cnt = 1;
- for (i = 18;i >= 0;i--) {
- if (R[l][i] >= 0 && R[l][i] <= r) {
- cnt += (1 << i);
- l = R[l][i];
- }
- }
- return cnt;
- }
- int main() {
- int N,i,j,mx,temp1,temp2,temp3,temp4,lo,hi,mid,ll,rr;
- set<pair<int,int>>::iterator it;
- scanf("%d",&N);
- for (i = 0;i < N;i++) {
- scanf("%d%d",&com[i].fi,&com[i].se);
- srt[i] = com[i];
- }
- sort(srt,srt + N,cmp);
- mx = 0;
- for (i = 0;i < N;i++) {
- if (srt[i].fi > mx) {
- unq.push_back(srt[i]);
- mx = srt[i].fi;
- }
- }
- memset(R,-1,sizeof(R));
- for (i = 0;i < unq.size();i++) {
- while (j < unq.size() && unq[j].fi <= unq[i].se)
- j++;
- if (j < unq.size())
- R[i][0] = j;
- }
- for (j = 1;j < 19;j++) {
- for (i = unq.size() - 1;i >= 0;i--) {
- if (R[i][j - 1] >= 0)
- R[i][j] = R[R[i][j - 1]][j - 1];
- }
- }
- s.insert({1,1000000000});
- for (i = 0;i < N;i++) {
- it = s.upper_bound({com[i].fi,INF});
- if (it == s.begin())
- continue;
- it--;
- temp1 = it->fi;
- temp2 = it->se;
- if (temp1 <= com[i].fi && temp2 >= com[i].se) {
- lo = -1;
- hi = unq.size();
- while ((hi - lo) > 1) {
- mid = (lo + hi) >> 1;
- if (unq[mid].se < com[i].fi)
- lo = mid;
- else
- hi = mid;
- }
- ll = lo;
- lo = 0;
- hi = unq.size();
- while ((hi - lo) > 1) {
- mid = (lo + hi) >> 1;
- if (unq[mid].fi <= com[i].se)
- lo = mid;
- else
- hi = mid;
- }
- rr = hi;
- temp3 = lower_bound(unq.begin(),unq.end(),make_pair(temp1,0)) - unq.begin();
- lo = 0;
- hi = unq.size();
- while ((hi - lo) > 1) {
- mid = (lo + hi) >> 1;
- if (unq[mid].se <= temp2)
- lo = mid;
- else
- hi = mid;
- }
- temp4 = lo;
- if (MIS(temp3,ll) + 1 + MIS(rr,temp4) == MIS(temp3,temp4)) {
- ans.push_back(i);
- s.erase(it);
- s.insert({temp1,com[i].fi - 1});
- s.insert({com[i].se + 1,temp2});
- }
- }
- }
- printf("%d\n",ans.size());
- for (int a : ans)
- printf("%d ",a + 1);
- printf("\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement