| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1092428 | juicy | Segments (IZhO18_segments) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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";
}
}
}