#include<bits/stdc++.h>
using namespace std;
const int N = 100000;
const int B = 1288;
void UGABUGA(bool f) {
if(!f) {
1/0;
}
}
struct SQRT {
struct obj {
int key;
int val;
obj(int key, int val) : key(key), val(val) {}
};
bool equal(obj a, obj b) {
return (a.key == b.key && a.val == b.val);
}
vector<obj> arr[N / B + 5];
vector<int> st[N / B + 5];
int sz = 0, b_num = 0;
void add(int key, int val) {
int block = 0;
while(block < b_num - 1 && (arr[block].empty() || arr[block].back().key < key))
block++;
int pos_arr = 0, pos_st = 0;
for(int i = 0; i < (int)arr[block].size(); i++) {
if(arr[block][i].key < key) pos_arr++;
if(st[block][i] < val) pos_st++;
}
if(!sz) b_num = 1;
sz++;
st[block].insert(st[block].begin() + pos_st, val);
arr[block].insert(arr[block].begin() + pos_arr, obj(key, val));
}
void del(int key, int val) {
int block = 0;
while(block < b_num - 1 && (arr[block].empty() || arr[block].back().key < key))
block++;
int pos_arr = 0, pos_st = 0;
for(int i = 0; i < (int)arr[block].size(); i++) {
if(arr[block][i].key < key) pos_arr++;
if(st[block][i] < val) pos_st++;
}
UGABUGA(pos_arr < (int)arr[block].size() && equal(arr[block][pos_arr], obj(key, val)));
arr[block].erase(arr[block].begin() + pos_arr);
UGABUGA(pos_st < (int)st[block].size() && st[block][pos_st] == val);
st[block].erase(st[block].begin() + pos_st);
sz--;
if(!sz) b_num = 0;
}
int get(int k, int x) {
int ans = 0;
int block_p = b_num - 1;
while(block_p >= 0 && (arr[block_p].empty() || arr[block_p].front().key >= k)) {
int lb = -1, rb = arr[block_p].size();
while(rb - lb > 1) {
int m = (lb + rb) / 2;
if(st[block_p][m] < x) lb = m;
else rb = m;
}
ans += lb + 1;
block_p--;
}
if(block_p < 0) return ans;
int arr_p = arr[block_p].size() - 1;
while(arr_p >= 0 && arr[block_p][arr_p].key >= k) {
ans += (arr[block_p][arr_p].val < x);
arr_p--;
}
return ans;
}
void normalize() {
vector<obj> v;
for(int i = 0; i < b_num; i++) {
for(obj x : arr[i])
v.push_back(x);
}
for(int i = 0; i < sz; i++) {
if(i % B == 0 && !arr[i / B].empty()) {
arr[i / B].clear();
st[i / B].clear();
}
arr[i / B].push_back(v[i]);
st[i / B].push_back(v[i].val);
}
b_num = (sz - 1) / B + 1;
for(int i = 0; i < b_num; i++)
sort(st[i].begin(), st[i].end());
}
};
SQRT ll, rr;
int lastans;
vector<pair<int, int>> v;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
v.push_back({-1, -1});
int n, t;
cin >> n >> t;
for(int iter = 1; iter <= n; iter++) {
int type;
cin >> type;
if(type == 1) {
int l, r;
cin >> l >> r;
l = (l ^ (t * lastans));
r = (r ^ (t * lastans));
if(l > r) swap(l, r);
v.push_back({l, r});
int len = r - l + 1;
ll.add(len, l);
rr.add(len, r);
}
if(type == 2) {
int id;
cin >> id;
ll.del(v[id].second - v[id].first + 1, v[id].first);
rr.del(v[id].second - v[id].first + 1, v[id].second);
}
if(type == 3) {
int l, r, k;
cin >> l >> r >> k;
l = (l ^ (t * lastans));
r = (r ^ (t * lastans));
if(l > r) swap(l, r);
lastans = 0;
if(r - l + 1 < k) {
cout << 0 << '\n';
continue;
}
lastans = ll.get(k, r - k + 2) - rr.get(k, l + k - 1);
cout << lastans << '\n';
}
if(iter % B == 0) {
ll.normalize();
rr.normalize();
}
}
}
Compilation message
segments.cpp: In function 'void UGABUGA(bool)':
segments.cpp:10:10: warning: division by zero [-Wdiv-by-zero]
10 | 1/0;
| ~^~
segments.cpp:10:10: warning: statement has no effect [-Wunused-value]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
24 ms |
564 KB |
Output is correct |
6 |
Correct |
17 ms |
496 KB |
Output is correct |
7 |
Correct |
7 ms |
340 KB |
Output is correct |
8 |
Correct |
15 ms |
496 KB |
Output is correct |
9 |
Correct |
16 ms |
468 KB |
Output is correct |
10 |
Correct |
17 ms |
496 KB |
Output is correct |
11 |
Correct |
13 ms |
468 KB |
Output is correct |
12 |
Correct |
13 ms |
496 KB |
Output is correct |
13 |
Correct |
17 ms |
480 KB |
Output is correct |
14 |
Correct |
18 ms |
560 KB |
Output is correct |
15 |
Correct |
4 ms |
340 KB |
Output is correct |
16 |
Correct |
3 ms |
340 KB |
Output is correct |
17 |
Correct |
13 ms |
444 KB |
Output is correct |
18 |
Correct |
17 ms |
536 KB |
Output is correct |
19 |
Correct |
17 ms |
340 KB |
Output is correct |
20 |
Correct |
13 ms |
452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
733 ms |
3740 KB |
Output is correct |
2 |
Correct |
735 ms |
3848 KB |
Output is correct |
3 |
Correct |
730 ms |
3980 KB |
Output is correct |
4 |
Correct |
756 ms |
4104 KB |
Output is correct |
5 |
Correct |
831 ms |
6452 KB |
Output is correct |
6 |
Correct |
808 ms |
6616 KB |
Output is correct |
7 |
Correct |
773 ms |
4008 KB |
Output is correct |
8 |
Correct |
778 ms |
3880 KB |
Output is correct |
9 |
Correct |
832 ms |
3764 KB |
Output is correct |
10 |
Correct |
528 ms |
2052 KB |
Output is correct |
11 |
Correct |
605 ms |
2448 KB |
Output is correct |
12 |
Correct |
966 ms |
5292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
988 KB |
Output is correct |
2 |
Correct |
40 ms |
980 KB |
Output is correct |
3 |
Correct |
93 ms |
1140 KB |
Output is correct |
4 |
Correct |
43 ms |
996 KB |
Output is correct |
5 |
Correct |
849 ms |
5376 KB |
Output is correct |
6 |
Correct |
803 ms |
4320 KB |
Output is correct |
7 |
Correct |
846 ms |
5168 KB |
Output is correct |
8 |
Correct |
784 ms |
6440 KB |
Output is correct |
9 |
Correct |
813 ms |
6224 KB |
Output is correct |
10 |
Incorrect |
747 ms |
4512 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
1020 KB |
Output is correct |
2 |
Correct |
46 ms |
948 KB |
Output is correct |
3 |
Correct |
44 ms |
1052 KB |
Output is correct |
4 |
Correct |
52 ms |
964 KB |
Output is correct |
5 |
Correct |
819 ms |
5604 KB |
Output is correct |
6 |
Correct |
336 ms |
1672 KB |
Output is correct |
7 |
Correct |
817 ms |
5956 KB |
Output is correct |
8 |
Correct |
435 ms |
2372 KB |
Output is correct |
9 |
Incorrect |
605 ms |
3868 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
24 ms |
564 KB |
Output is correct |
6 |
Correct |
17 ms |
496 KB |
Output is correct |
7 |
Correct |
7 ms |
340 KB |
Output is correct |
8 |
Correct |
15 ms |
496 KB |
Output is correct |
9 |
Correct |
16 ms |
468 KB |
Output is correct |
10 |
Correct |
17 ms |
496 KB |
Output is correct |
11 |
Correct |
13 ms |
468 KB |
Output is correct |
12 |
Correct |
13 ms |
496 KB |
Output is correct |
13 |
Correct |
17 ms |
480 KB |
Output is correct |
14 |
Correct |
18 ms |
560 KB |
Output is correct |
15 |
Correct |
4 ms |
340 KB |
Output is correct |
16 |
Correct |
3 ms |
340 KB |
Output is correct |
17 |
Correct |
13 ms |
444 KB |
Output is correct |
18 |
Correct |
17 ms |
536 KB |
Output is correct |
19 |
Correct |
17 ms |
340 KB |
Output is correct |
20 |
Correct |
13 ms |
452 KB |
Output is correct |
21 |
Correct |
733 ms |
3740 KB |
Output is correct |
22 |
Correct |
735 ms |
3848 KB |
Output is correct |
23 |
Correct |
730 ms |
3980 KB |
Output is correct |
24 |
Correct |
756 ms |
4104 KB |
Output is correct |
25 |
Correct |
831 ms |
6452 KB |
Output is correct |
26 |
Correct |
808 ms |
6616 KB |
Output is correct |
27 |
Correct |
773 ms |
4008 KB |
Output is correct |
28 |
Correct |
778 ms |
3880 KB |
Output is correct |
29 |
Correct |
832 ms |
3764 KB |
Output is correct |
30 |
Correct |
528 ms |
2052 KB |
Output is correct |
31 |
Correct |
605 ms |
2448 KB |
Output is correct |
32 |
Correct |
966 ms |
5292 KB |
Output is correct |
33 |
Correct |
42 ms |
1020 KB |
Output is correct |
34 |
Correct |
46 ms |
948 KB |
Output is correct |
35 |
Correct |
44 ms |
1052 KB |
Output is correct |
36 |
Correct |
52 ms |
964 KB |
Output is correct |
37 |
Correct |
819 ms |
5604 KB |
Output is correct |
38 |
Correct |
336 ms |
1672 KB |
Output is correct |
39 |
Correct |
817 ms |
5956 KB |
Output is correct |
40 |
Correct |
435 ms |
2372 KB |
Output is correct |
41 |
Incorrect |
605 ms |
3868 KB |
Output isn't correct |
42 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
24 ms |
564 KB |
Output is correct |
6 |
Correct |
17 ms |
496 KB |
Output is correct |
7 |
Correct |
7 ms |
340 KB |
Output is correct |
8 |
Correct |
15 ms |
496 KB |
Output is correct |
9 |
Correct |
16 ms |
468 KB |
Output is correct |
10 |
Correct |
17 ms |
496 KB |
Output is correct |
11 |
Correct |
13 ms |
468 KB |
Output is correct |
12 |
Correct |
13 ms |
496 KB |
Output is correct |
13 |
Correct |
17 ms |
480 KB |
Output is correct |
14 |
Correct |
18 ms |
560 KB |
Output is correct |
15 |
Correct |
4 ms |
340 KB |
Output is correct |
16 |
Correct |
3 ms |
340 KB |
Output is correct |
17 |
Correct |
13 ms |
444 KB |
Output is correct |
18 |
Correct |
17 ms |
536 KB |
Output is correct |
19 |
Correct |
17 ms |
340 KB |
Output is correct |
20 |
Correct |
13 ms |
452 KB |
Output is correct |
21 |
Correct |
733 ms |
3740 KB |
Output is correct |
22 |
Correct |
735 ms |
3848 KB |
Output is correct |
23 |
Correct |
730 ms |
3980 KB |
Output is correct |
24 |
Correct |
756 ms |
4104 KB |
Output is correct |
25 |
Correct |
831 ms |
6452 KB |
Output is correct |
26 |
Correct |
808 ms |
6616 KB |
Output is correct |
27 |
Correct |
773 ms |
4008 KB |
Output is correct |
28 |
Correct |
778 ms |
3880 KB |
Output is correct |
29 |
Correct |
832 ms |
3764 KB |
Output is correct |
30 |
Correct |
528 ms |
2052 KB |
Output is correct |
31 |
Correct |
605 ms |
2448 KB |
Output is correct |
32 |
Correct |
966 ms |
5292 KB |
Output is correct |
33 |
Correct |
72 ms |
988 KB |
Output is correct |
34 |
Correct |
40 ms |
980 KB |
Output is correct |
35 |
Correct |
93 ms |
1140 KB |
Output is correct |
36 |
Correct |
43 ms |
996 KB |
Output is correct |
37 |
Correct |
849 ms |
5376 KB |
Output is correct |
38 |
Correct |
803 ms |
4320 KB |
Output is correct |
39 |
Correct |
846 ms |
5168 KB |
Output is correct |
40 |
Correct |
784 ms |
6440 KB |
Output is correct |
41 |
Correct |
813 ms |
6224 KB |
Output is correct |
42 |
Incorrect |
747 ms |
4512 KB |
Output isn't correct |
43 |
Halted |
0 ms |
0 KB |
- |