fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. // #define int long long
  4. const int N = 2e5 + 5, MX = 2e5;
  5.  
  6. struct node {
  7. int mx, lazy;
  8. } t[N << 2];
  9.  
  10. struct node1{
  11. int mx, pos;
  12. } t1[N << 2];
  13.  
  14. int n, k, ss[N];
  15. map<pair<int, int>, vector<int>> mp;
  16. vector<int> val[N];
  17.  
  18. void down(int p) {
  19. if (!t[p].lazy) return;
  20.  
  21. t[p << 1].lazy += t[p].lazy;
  22. t[p << 1 | 1].lazy += t[p].lazy;
  23.  
  24. t[p << 1].mx += t[p].lazy;
  25. t[p << 1 | 1].mx += t[p].lazy;
  26.  
  27. t[p].lazy = 0;
  28. }
  29.  
  30. void upd(int p, int l, int r, int u, int v) {
  31. if (l > v || r < u) return;
  32. if (u <= l && r <= v) {
  33. t[p].lazy--;
  34. t[p].mx--;
  35. return;
  36. }
  37. down(p);
  38. int mid = (l + r) / 2;
  39. upd(p << 1, l, mid, u, v);
  40. upd(p << 1 | 1, mid + 1, r, u, v);
  41. t[p].mx = max(t[p << 1].mx, t[p << 1 | 1].mx);
  42. }
  43.  
  44. int get(int p, int l, int r) {
  45. if (l == r) return (t[p].mx > k ? l : -1);
  46. int mid = (l + r) / 2;
  47. down(p);
  48. if (t[p << 1].mx > k) return get(p << 1, l, mid);
  49. return get(p << 1 | 1, mid + 1, r);
  50. }
  51.  
  52. void init(int p, int l, int r) {
  53. if (l == r) {
  54. t1[p].mx = (val[l].size() ? val[l].back() : 0);
  55. t1[p].pos = l;
  56. return;
  57. }
  58. int mid = (l + r) / 2;
  59. init(p << 1, l, mid);
  60. init(p << 1 | 1, mid + 1, r);
  61. t1[p].mx = max(t1[p << 1].mx, t1[p << 1 | 1].mx);
  62. t1[p].pos = (t1[p << 1].mx > t1[p << 1 | 1].mx ? t1[p << 1].pos : t1[p << 1 | 1].pos);
  63. }
  64.  
  65. void ers(int p, int l, int r, int pos) {
  66. if (l == r) {
  67. if (val[l].size()) val[l].pop_back();
  68. if (val[l].size()) t1[p].mx = val[l].back();
  69. else t1[p].mx = 0;
  70. t1[p].pos = l;
  71. return;
  72. }
  73. int mid = (l + r) / 2;
  74. if (pos <= mid) ers(p << 1, l, mid, pos);
  75. else ers(p << 1 | 1, mid + 1, r, pos);
  76. t1[p].mx = max(t1[p << 1].mx, t1[p << 1 | 1].mx);
  77. t1[p].pos = (t1[p << 1].mx > t1[p << 1 | 1].mx ? t1[p << 1].pos : t1[p << 1 | 1].pos);
  78. }
  79.  
  80. pair<int, int> get1(int p, int l, int r, int u) {
  81. if (r <= u) return {t1[p].pos, t1[p].mx};
  82. if (l > u) return pair<int, int>{-1, -1};
  83. int mid = (l + r) / 2;
  84. pair<int, int> p1 = get1(p << 1, l, mid, u);
  85. pair<int, int> p2 = get1(p << 1 | 1, mid + 1, r, u);
  86. return (p1.second > p2.second ? p1 : p2);
  87. }
  88.  
  89. void init1(int p, int l, int r) {
  90. if (l == r) {
  91. t[p].mx = ss[l];
  92. return;
  93. }
  94. int mid = (l + r) / 2;
  95. init1(p << 1, l, mid);
  96. init1(p << 1 | 1, mid + 1, r);
  97. t[p].mx = max(t[p << 1].mx, t[p << 1 | 1].mx);
  98. }
  99.  
  100. void solve() {
  101. cin >> n >> k;
  102. for (int i = 1; i <= n; ++i) {
  103. static int fi, se;
  104. cin >> fi >> se;
  105. val[fi].emplace_back(se);
  106. mp[{fi,se}].emplace_back(i);
  107. ss[fi]++, ss[se+1]--;
  108. }
  109. for (int i = 1; i < N; ++i) {
  110. ss[i] += ss[i-1];
  111. sort(val[i].begin(), val[i].end());
  112. }
  113. init1(1, 1, MX);
  114. init(1, 1, MX);
  115. int p = get(1, 1, MX);
  116. int ans = 0;
  117. vector<int> vt;
  118. while(p != -1) {
  119. pair<int, int> del = get1(1, 1, MX, p);
  120. int poss = mp[{del.first, del.second}].back();
  121. mp[{del.first, del.second}].pop_back();
  122. ans++; vt.emplace_back(poss);
  123. upd(1, 1, MX, del.first, del.second);
  124. ers(1, 1, MX, del.first);
  125. p = get(1, 1, MX);
  126. }
  127. cout << ans << '\n';
  128. for (int x : vt) cout << x << ' ';
  129. }
  130.  
  131. signed main() {
  132. cin.tie(0) -> sync_with_stdio(0);
  133. int tc = 1; // cin >> tc;
  134. while(tc--) solve();
  135. }
Success #stdin #stdout 0.01s 20192KB
stdin
Standard input is empty
stdout
0