fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/KsuR2Q
language:
C++14 (gcc 8.3)
created:
35 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!