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;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
const int maxn = 1e6 + 10;
struct interval {
int l,r;
bool operator<(const interval& o) const {
return r-l<o.r-o.l;
}
};
const int B = 1500;
struct {
vector<interval> v;
vector<interval> w;
vector<vector<int>> L, R;
void rebuild() {
w.insert(w.end(),v.begin(),v.end());
sort(w.begin(),w.end());
v.clear();
int len = w.size();
L.clear();
R.clear();
L.resize(len/B);
R.resize(len/B);
for (int i=0; i<len; i++) {
L[i/B].push_back(w[i].l);
R[i/B].push_back(w[i].r);
}
for (auto &p: L) {
sort(p.begin(),p.end());
}
for (auto &p: R) {
sort(p.begin(),p.end());
}
}
void insert(int l, int r) {
v.push_back({l,r});
if ((int)v.size()==B) {
rebuild();
}
}
int solve(int l, int r, int k) {
int res = 0;
for (auto p: v) {
res += (min(r,p.r)-max(l,p.l)+1>=k);
}
assert((int)w.size()%B==0);
for (int i=0; i+B<=(int)w.size(); i+=B) {
int e = i+B-1;
res += e-i+1;
if (w[i].r-w[i].l+1 >= k) {
res -= (lower_bound(R[i/B].begin(),R[i/B].end(),l+k-1)-R[i/B].begin()); // end too early
res -= (L[i/B].end() - upper_bound(L[i/B].begin(),L[i/B].end(),r-k+1)); // start too late
} else if (w[e].r-w[e].l+1 >= k) {
for (int j=e; j>=i; j--) {
if (w[j].r-w[j].l+1<k) {
res--;
}
}
}
}
return res;
}
} alive, dead;
int n,t;
int lastans=0;
interval arr[maxn];
int idx=0;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>t;
while (n--) {
int op;
cin>>op;
if (op==1) {
int a,b;
cin>>a>>b;
int l=a^(t*lastans);
int r=b^(t*lastans);
if (l>r) swap(l,r);
arr[++idx] = interval{l,r};
alive.insert(arr[idx].l,arr[idx].r);
} else if (op==2) {
int id;
cin>>id;
dead.insert(arr[id].l,arr[id].r);
} else if (op==3) {
int a,b,k;
cin>>a>>b>>k;
int l=a^(t*lastans);
int r=b^(t*lastans);
if (l>r) swap(l,r);
lastans = alive.solve(l,r,k) - dead.solve(l,r,k);
cout<<lastans<<"\n";
} else assert(false);
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |