#include <bits/stdc++.h>
#define pii pair<int, int>
#define X first
#define Y second
#define pb push_back
using namespace std;
const int SQR = 450;
const int N = 4 * 1e5 + 10;
int n, xr, lastans, pos[N];
int b_cnt; //num. of buckets
int cnt; //num of diff. intervals
bool ban[N];
pii intv[N];
vector<vector<int>> lft, rgt;
vector<pii> bkt, bkt2, add;
vector<int> vl, vr, rem;
int intersect(pii a, pii b){
if(b.X > a.Y || a.X > b.Y) return 0;
return min(a.Y, b.Y) - max(a.X, b.X) + 1;
}
void bucket(){
for(int x : rem) ban[x] = true;
sort(add.begin(), add.end());
int p1 = 0;
int p2 = 0;
lft.clear();
rgt.clear();
while(p1 < add.size() || p2 < bkt.size()){
if(p1 < add.size() && p2 < bkt.size()){
if(add[p1].X < bkt[p2].X){
bkt2.pb(add[p1]);
p1++;
} else {
bkt2.pb(bkt[p2]);
p2++;
}
} else if(p1 < add.size()){
bkt2.pb(add[p1]);
p1++;
} else {
bkt2.pb(bkt[p2]);
p2++;
}
}
bkt.clear();
for(pii x : bkt2){
if(!ban[x.Y])
bkt.pb(x);
}
bkt2.clear();
for(pii x : bkt){
vl.pb(intv[x.Y].X);
vr.pb(intv[x.Y].Y);
if(vl.size() >= SQR){
sort(vl.begin(), vl.end());
sort(vr.begin(), vr.end());
lft.pb(vl);
rgt.pb(vr);
vl.clear();
vr.clear();
}
}
if(!vl.empty()){
sort(vl.begin(), vl.end());
sort(vr.begin(), vr.end());
lft.pb(vl);
rgt.pb(vr);
vl.clear();
vr.clear();
}
for(int x : rem) ban[x] = false;
rem.clear();
add.clear();
b_cnt = lft.size();
}
int main(){
for(int i = 0; i < N; i++) pos[i] = i / SQR;
scanf("%d%d", &n, &xr);
for(int i = 0; i < n; i++){
int t;
cin >> t;
if(t == 1){
int l, r;
scanf("%d%d", &l, &r);
l = l ^ (xr * lastans);
r = r ^ (xr * lastans);
if(l > r) swap(l, r);
intv[++cnt] = {l, r};
add.pb({r - l + 1, cnt});
} else if(t == 2){
int ind;
scanf("%d", &ind);
rem.pb(ind);
} else {
int l, r, k, ans = 0;
scanf("%d%d%d", &l, &r, &k);
l = l ^ (xr * lastans);
r = r ^ (xr * lastans);
if(l > r) swap(l, r);
for(int x : rem){
// cout << intv[x].X << " " << intv[x].Y << " " << l << " " << r << ": " << intersect(intv[x], {l, r}) << " -\n";
if(intersect(intv[x], {l, r}) >= k) ans--;
}
for(pii x : add){
// cout << intv[x.Y].X << " " << intv[x.Y].Y << " " << l << " " << r << ": " << intersect(intv[x.Y], {l, r}) << " +\n";
if(intersect(intv[x.Y], {l, r}) >= k) ans++;
}
int lo = 0, hi = bkt.size();
while(hi - lo > 1){
int mi = (lo + hi) / 2;
if(bkt[mi].X < k)
lo = mi;
else
hi = mi;
}
int b = pos[hi];
while(hi < bkt.size() && pos[hi] == b){
if(intersect(intv[bkt[hi].Y], {l, r}) >= k) ans++;
hi++;
}
b++;
for(b; b < b_cnt; b++){
ans += lft[b].size();
ans -= upper_bound(rgt[b].begin(), rgt[b].end(), l + k) - rgt[b].begin();
ans -= lft[b].end() - upper_bound(lft[b].begin(), lft[b].end(), r - k);
}
cout << ans << "\n";
lastans = ans;
}
if(add.size() + rem.size() >= SQR){
bucket();
}
}
return 0;
}
Compilation message
segments.cpp: In function 'void bucket()':
segments.cpp:37:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | while(p1 < add.size() || p2 < bkt.size()){
| ~~~^~~~~~~~~~~~
segments.cpp:37:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | while(p1 < add.size() || p2 < bkt.size()){
| ~~~^~~~~~~~~~~~
segments.cpp:38:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | if(p1 < add.size() && p2 < bkt.size()){
| ~~~^~~~~~~~~~~~
segments.cpp:38:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | if(p1 < add.size() && p2 < bkt.size()){
| ~~~^~~~~~~~~~~~
segments.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | } else if(p1 < add.size()){
| ~~~^~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:137:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | while(hi < bkt.size() && pos[hi] == b){
| ~~~^~~~~~~~~~~~
segments.cpp:142:8: warning: statement has no effect [-Wunused-value]
142 | for(b; b < b_cnt; b++){
| ^
segments.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | scanf("%d%d", &n, &xr);
| ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%d%d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:109:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | scanf("%d", &ind);
| ~~~~~^~~~~~~~~~~~
segments.cpp:113:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | scanf("%d%d%d", &l, &r, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
1892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
762 ms |
3696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
150 ms |
2252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
131 ms |
2156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
1892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
1892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
