| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 93889 | dalgerok | Segments (IZhO18_segments) | C++14 | 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;
const int N = 2e5 + 5, S = 500, M = N / S + 5;
int n, t, ans;
int sz, alive, L[N], R[N];
pair < int, int > a[N];
int add[S], sz_add, del[S], sz_del;
bool kill[M];
int sz_l[M], sz_r[M];
int b_l[M][S], b_r[M][S];
int m;
inline void rebuild(){
m = 0;
for(int i = 1; i <= sz; i++){
if(kill[i] == false){
a[m++] = make_pair(R[i] - L[i] + 1, i);
}
}
sort(a, a + m);
sz_add = sz_del = 0;
for(int i = 0; i <= m / S; i++){
sz_l[i] = sz_r[i] = 0;
}
for(int i = 0; i < m; i++){
b_l[i / S][sz_l[i / S]++] = L[a[i].second];
b_r[i / S][sz_r[i / S]++] = R[a[i].second];
}
for(int i = 0; i <= m / S; i++){
sort(b_l[i], b_l[i] + sz_l[i]);
sort(b_r[i], b_r[i] + sz_r[i]);
}
}
inline int intersect(int l1, int r1, int l2, int r2){
return max(0, min(r1, r2) - max(l1, l2) + 1);
}
/// number of L > x from l to r
inline int calcL(int l, int r, int x){
int res = 0;
int bl = l / S, br = r / S;
if(bl == br){
for(int i = l; i <= r; i++){
res += (L[a[i].second] > x);
}
return res;
}
for(int i = bl + 1; i <= br - 1; i++){
int j = lower_bound(b_l[i], b_l[i] + sz_l[i], x + 1) - b_l[i];
res += S - j;
}
for(int i = l; i < (bl + 1) * S; i++){
res += (L[a[i].second] > x);
}
for(int i = br * S; i <= r; i++){
res += (L[a[i].second] > x);
}
return res;
}
/// number of R < x from l to r
inline int calcR(int l, int r, int x){
int res = 0;
int bl = l / S, br = r / S;
if(bl == br){
for(int i = l; i <= r; i++){
res += (R[a[i].second] < x);
}
return res;
}
for(int i = bl + 1; i <= br - 1; i++){
int j = lower_bound(b_r[i], b_r[i] + sz_r[i], x) - b_r[i];
res += j;
}
for(int i = l; i < (bl + 1) * S; i++){
res += (R[a[i].second] < x);
}
for(int i = br * S; i <= r; i++){
res += (R[a[i].second] < x);
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> t;
for(int i = 1; i <= n; i++){
if(i % S == 0){
rebuild();
}
int type;
cin >> type;
if(type == 1){
int l, r;
cin >> l >> r;
l ^= (1LL * t * ans);
r ^= (1LL * t * ans);
if(l > r){
swap(l, r);
}
sz += 1;
L[sz] = l;
R[sz] = r;
add[sz_add++] = sz;
alive += 1;
}
else if(type == 2){
int x;
cin >> x;
del[sz_del++] = x;
kill[x] = true;
alive -= 1;
}
else{
int l, r, k;
cin >> l >> r >> k;
l ^= (1LL * t * ans);
r ^= (1LL * t * ans);
if(l > r){
swap(l, r);
}
if(r - l + 1 < k){
ans = 0;
cout << "0\n";
continue;
}
int res = 0;
for(int j = 0; j < sz_add; j++){
res += (intersect(l, r, L[add[j]], R[add[j]]) < k);
}
for(int j = 0; j < sz_del; j++){
res -= (intersect(l, r, L[del[j]], R[del[j]]) < k);
}
int pos = lower_bound(a, a + m, make_pair(k, 0)) - a;
res += pos;
res += calcL(pos, m - 1, r - k + 1);
res += calcR(pos, m - 1, l + k - 1);
ans = alive - res;
cout << ans << "\n";
}
}
}