Advertisement
Guest User

Untitled

a guest
Dec 7th, 2019
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.28 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. #include <set>
  4. #include <cstring>
  5. #include <map>
  6. #include <algorithm>
  7. // APIO '09 P2 - The Siruseri Convention Centre
  8.  
  9. #define fi first
  10. #define se second
  11. #define INF 0x3f3f3f3f
  12.  
  13. using namespace std;
  14.  
  15. pair<int,int> com[200005],srt[200005];
  16. vector<pair<int,int>> unq;
  17. set<pair<int,int>> s;
  18. int R[200005][19];
  19. vector<int> ans;
  20.  
  21. bool cmp(pair<int,int> p1,pair<int,int> p2) {
  22. if (p1.se == p2.se)
  23. return p1.fi > p2.fi;
  24.  
  25. return p1.se < p2.se;
  26. }
  27.  
  28. int MIS(int l,int r) {
  29. if (l == -1 || r == -1)
  30. return 0;
  31. if (l > r)
  32. return 0;
  33.  
  34. int i,cnt;
  35.  
  36. cnt = 1;
  37. for (i = 18;i >= 0;i--) {
  38. if (R[l][i] >= 0 && R[l][i] <= r) {
  39. cnt += (1 << i);
  40. l = R[l][i];
  41. }
  42. }
  43.  
  44. return cnt;
  45. }
  46.  
  47. int main() {
  48. int N,i,j,mx,temp1,temp2,temp3,temp4,lo,hi,mid,ll,rr;
  49. set<pair<int,int>>::iterator it;
  50.  
  51. scanf("%d",&N);
  52.  
  53. for (i = 0;i < N;i++) {
  54. scanf("%d%d",&com[i].fi,&com[i].se);
  55. srt[i] = com[i];
  56. }
  57.  
  58. sort(srt,srt + N,cmp);
  59.  
  60. mx = 0;
  61. for (i = 0;i < N;i++) {
  62. if (srt[i].fi > mx) {
  63. unq.push_back(srt[i]);
  64. mx = srt[i].fi;
  65. }
  66. }
  67.  
  68. memset(R,-1,sizeof(R));
  69.  
  70. for (i = 0;i < unq.size();i++) {
  71. while (j < unq.size() && unq[j].fi <= unq[i].se)
  72. j++;
  73.  
  74. if (j < unq.size())
  75. R[i][0] = j;
  76. }
  77.  
  78. for (j = 1;j < 19;j++) {
  79. for (i = unq.size() - 1;i >= 0;i--) {
  80. if (R[i][j - 1] >= 0)
  81. R[i][j] = R[R[i][j - 1]][j - 1];
  82. }
  83. }
  84.  
  85. s.insert({1,1000000000});
  86. for (i = 0;i < N;i++) {
  87. it = s.upper_bound({com[i].fi,INF});
  88.  
  89. if (it == s.begin())
  90. continue;
  91.  
  92. it--;
  93. temp1 = it->fi;
  94. temp2 = it->se;
  95.  
  96. if (temp1 <= com[i].fi && temp2 >= com[i].se) {
  97. lo = -1;
  98. hi = unq.size();
  99.  
  100. while ((hi - lo) > 1) {
  101. mid = (lo + hi) >> 1;
  102.  
  103. if (unq[mid].se < com[i].fi)
  104. lo = mid;
  105. else
  106. hi = mid;
  107. }
  108.  
  109. ll = lo;
  110.  
  111. lo = 0;
  112. hi = unq.size();
  113.  
  114. while ((hi - lo) > 1) {
  115. mid = (lo + hi) >> 1;
  116.  
  117. if (unq[mid].fi <= com[i].se)
  118. lo = mid;
  119. else
  120. hi = mid;
  121. }
  122.  
  123. rr = hi;
  124.  
  125. temp3 = lower_bound(unq.begin(),unq.end(),make_pair(temp1,0)) - unq.begin();
  126.  
  127. lo = 0;
  128. hi = unq.size();
  129.  
  130. while ((hi - lo) > 1) {
  131. mid = (lo + hi) >> 1;
  132.  
  133. if (unq[mid].se <= temp2)
  134. lo = mid;
  135. else
  136. hi = mid;
  137. }
  138.  
  139. temp4 = lo;
  140.  
  141. if (MIS(temp3,ll) + 1 + MIS(rr,temp4) == MIS(temp3,temp4)) {
  142. ans.push_back(i);
  143. s.erase(it);
  144. s.insert({temp1,com[i].fi - 1});
  145. s.insert({com[i].se + 1,temp2});
  146. }
  147. }
  148. }
  149.  
  150. printf("%d\n",ans.size());
  151. for (int a : ans)
  152. printf("%d ",a + 1);
  153. printf("\n");
  154.  
  155. return 0;
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement