Submission #1092429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092429		juicy	Segments (IZhO18_segments)	C++17	75 / 100	5065 ms	10752 KiB

segments

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 2e5 + 5, B = 500;
 
int n;
int lt[N / B + 3], rt[N / B + 3], blk[N], pos[N];
bool on[N];
array<int, 2> a[N];
vector<int> L[N / B + 3], R[N / B + 3];
vector<array<int, 2>> cl, cr;
 
void bld(int c) {
  vector<array<int, 2>>().swap(cl);
  vector<array<int, 2>>().swap(cr);
  for (int i = 1; i < c; ++i) {
    if (on[i]) {
      int len = a[i][1] - a[i][0] + 1;
      cl.push_back({len, a[i][0]});
      cr.push_back({len, a[i][1]});
    }
  }
  sort(cl.begin(), cl.end());
  sort(cr.begin(), cr.end());
  for (int i = blk[0]; i <= blk[c]; ++i) {
    vector<int>().swap(L[i]);
    vector<int>().swap(R[i]);
  }
  for (int i = 0; i < cl.size(); ++i) {
    L[blk[i]].push_back(cl[i][1]);
    R[blk[i]].push_back(cr[i][1]);
  }
  for (int i = 0; i <= blk[c]; ++i) {
    sort(L[i].begin(), L[i].end());
    sort(R[i].begin(), R[i].end());
  }
}
 
int cL(int l, int r, int x) {
  if (blk[l] == blk[r]) {
    int res = 0;
    for (int i = l; i <= r; ++i) {
      res += cl[i][1] > x;
    }
    return res;
  } 
  int res = 0;
  for (int i = l; i < lt[blk[l] + 1]; ++i) {
    res += cl[i][1] > x;
  }
  for (int i = blk[l] + 1; i < blk[r]; ++i) {
    res += L[i].end() - upper_bound(L[i].begin(), L[i].end(), x);
  }  
  for (int i = rt[blk[r] - 1] + 1; i <= r; ++i) {
    res += cl[i][1] > x;
  }
  return res;
}
 
int cR(int l, int r, int x) {
  if (blk[l] == blk[r]) {
    int res = 0;
    for (int i = l; i <= r; ++i) {
      res += cr[i][1] < x;
    }
    return res;
  } 
  int res = 0;
  for (int i = l; i < lt[blk[l] + 1]; ++i) {
    res += cr[i][1] < x;
  }
  for (int i = blk[l] + 1; i < blk[r]; ++i) {
    res += lower_bound(R[i].begin(), R[i].end(), x) - R[i].begin();
  }  
  for (int i = rt[blk[r] - 1] + 1; i <= r; ++i) {
    res += cr[i][1] < x;
  }
  return res;
} 
 
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  int c; cin >> n >> c;
  for (int i = 0; i < n; ++i) {
    blk[i] = i / B;
    rt[blk[i]] = i;
  }
  for (int i = n - 1; ~i; --i) {
    lt[blk[i]] = i;
  }
  int id = 0, lst = 0, cnt = 0;
  for (int i = 1; i <= n; ) {
    bld(i);
    int j = min(n, i + B - 1), b = i;
    for (; i <= j; ++i) {
      int t; cin >> t;
      if (t == 1) {
        int s, e; cin >> s >> e;
        s ^= c * lst;
        e ^= c * lst;
        if (s > e) {
          swap(s, e);
        }
        on[i] = 1;
        a[i] = {s, e};
        pos[++id] = i;
        ++cnt;
      } else if (t == 2) {
        int id; cin >> id;
        id = pos[id];
        on[id] = 0;
        --cnt;
        if (id < b) {
          a[i] = a[id];
        } else {
          a[i] = {-1, -1};
        }
        a[id] = {-1, -1};
      } else {
        a[i] = {-1, -1};
        int l, r, k; cin >> l >> r >> k;
        l ^= c * lst;
        r ^= c * lst;
        if (l > r) {
          swap(l, r);
        }
        if (r - l + 1 < k) {
          cout << (lst = 0) << "\n";
          continue;
        }
        lst = 0;
        if (cl.size()) {
          int p = lower_bound(cl.begin(), cl.end(), array<int, 2>{k}) - cl.begin();
          lst += p;
          if (p < cl.size()) {
            lst += cL(p, cl.size() - 1, r - k + 1) + cR(p, cl.size() - 1, l + k - 1);
          }
        }
        for (int ii = b; ii < i; ++ii) {
          if (on[ii]) {
            lst += min(a[ii][1], r) - max(a[ii][0], l) + 1 < k; 
          } else if (~a[ii][0]) {
            lst -= min(a[ii][1], r) - max(a[ii][0], l) + 1 < k;
          }
        }
        cout << (lst = cnt - lst) << "\n";
      }
    }
  } 
  return 0;
}

Compilation message (stderr)

segments.cpp: In function 'void bld(int)':
segments.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for (int i = 0; i < cl.size(); ++i) {
      |                   ~~^~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:143:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |           if (p < cl.size()) {
      |               ~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 0 / 25