Submission #395511

#	Time	Username	Problem	Language	Result	Execution time	Memory
395511		rama_pang	Segments (IZhO18_segments)	C++17	100 / 100	1963 ms	10604 KiB

segments

#include <bits/stdc++.h>
using namespace std;

const int BLOCK = 1800;
const int BSIZE = 200005 / BLOCK + 5;

class Solver {
 public:
  vector<pair<int, int>> pending;
  vector<pair<int, int>> intervals;

  vector<int> lengths[BSIZE]; // (r - l + 1)
  pair<int, int> minmaxl[BSIZE]; // min and max l in blockslr[]
  vector<pair<int, int>> blockslr[BSIZE]; // (l, r)

  int Isect(int a, int b, int l, int r) {
    return max(0, min(b, r) - max(a, l) + 1);
  }

  void Insert(int l, int r) {
    pending.emplace_back(l, r);
    if (pending.size() >= BLOCK) {
      for (auto p : pending) intervals.emplace_back(p);
      sort(begin(intervals), end(intervals));
      pending.clear();

      for (int i = 0; i < int(intervals.size()); i += BLOCK) {
        int b = i / BLOCK;
        lengths[b].clear();
        blockslr[b].clear();
        minmaxl[b] = {intervals[i].first, intervals[i].first};
        for (int j = i; j < min(int(intervals.size()), i + BLOCK); j++) {
          lengths[b].emplace_back(intervals[j].second - intervals[j].first + 1);
          blockslr[b].emplace_back(intervals[j]);
          minmaxl[b].first  = min(minmaxl[b].first,  intervals[j].first);
          minmaxl[b].second = max(minmaxl[b].second, intervals[j].first);
        }
        sort(begin(lengths[b]), end(lengths[b]));
        sort(begin(blockslr[b]), end(blockslr[b]), [&](auto &x, auto &y) {
          return x.second < y.second;
        });
      }
    }
  }

  int Query(int l, int r, int k) {
    if (r - l + 1 < k) return 0;

    int res = 0;
    for (auto p : pending) res += Isect(p.first, p.second, l, r) >= k;

    for (int i = 0; i < int(intervals.size()); i += BLOCK) {
      int b = i / BLOCK;
      if (minmaxl[b].second < l) {
        // right endpoint must be >= l + k - 1
        int lo = 0, hi = int(blockslr[b].size());
        while (lo < hi) {
          int md = (lo + hi) / 2;
          if (blockslr[b][md].second >= l + k - 1) {
            hi = md;
          } else {
            lo = md + 1;
          }
        }
        res += int(blockslr[b].size()) - lo;
      } else if (minmaxl[b].first < l && l <= minmaxl[b].second) { // will only trigger once
        for (auto p : blockslr[b]) res += Isect(p.first, p.second, l, r) >= k;
      } else if (l <= minmaxl[b].first && minmaxl[b].second <= r - k + 1) {
        // must count interval length >= k
        int lo = 0, hi = int(lengths[b].size());
        while (lo < hi) {
          int md = (lo + hi) / 2;
          if (lengths[b][md] >= k) {
            hi = md;
          } else {
            lo = md + 1;
          }
        }
        res += int(lengths[b].size()) - lo;
      } else if (minmaxl[b].first <= r - k + 1 && r - k + 1 < minmaxl[b].second) { // will only trigger once
        for (auto p : blockslr[b]) res += Isect(p.first, p.second, l, r) >= k;
      } else if (r - k + 1 < minmaxl[b].first) {
        // interval intersect on < k points
      } else {
        assert(false);
      }
    }

    return res;
  }
} positive, negative;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, t;
  cin >> n >> t;

  int lastans = 0;
  vector<int> l, r;

  while (n--) {
    int type;
    cin >> type;
    if (type == 1) {
      int a, b;
      cin >> a >> b;
      a = (a ^ (t * lastans));
      b = (b ^ (t * lastans));
      if (a > b) swap(a, b);
      l.emplace_back(a);
      r.emplace_back(b);
      positive.Insert(a, b);
    } else if (type == 2) {
      int id;
      cin >> id;
      id--;
      negative.Insert(l[id], r[id]);
    } else if (type == 3) {
      int a, b, k;
      cin >> a >> b >> k;
      a = (a ^ (t * lastans));
      b = (b ^ (t * lastans));
      if (a > b) swap(a, b);
      lastans = positive.Query(a, b, k) - negative.Query(a, b, k);
      cout << lastans << '\n';
    }
  }
  return 0;
}

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