#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
const int K = 500;
int n, t;
pair<int, int> a[N];
multiset<pair<int, int> > active;
struct Data {
int l, r, x;
};
vector<Data> add;
vector<array<int, 3>> cur;
vector<int> b1[1000], b2[1000];
void build() {
cur.clear();
for(auto [x, y] : active) {
int len = y-x+1;
cur.push_back({len, x, y});
}
sort(cur.begin(), cur.end());
int m = (int)cur.size();
for(int i = 0; i <= (m-1)/K; ++i) {
b1[i].clear();
b2[i].clear();
}
for(int i = 0; i < m; ++i) {
b1[i/K].push_back(cur[i][1]);
b2[i/K].push_back(cur[i][2]);
}
for(int i = 0; i <= (m-1)/K; ++i) {
sort(b1[i].rbegin(), b1[i].rend());
sort(b2[i].begin(), b2[i].end());
}
add.clear();
}
int get(int l, int r, int k) {
if(r-l+1<k) {
return 0;
}
int res = 0;
int m = (int)cur.size();
for(int i = 0, id = 0; i < m; i += K, ++id) {
if(cur[i][0]<k) {
int j = min(m, i+K), old = i;
if(cur[j][0]<k) {
continue;
}
while(i<j) {
if(cur[i][0]>=k) {
res++;
if(cur[i][2]<l+k-1) {
res--;
}
if(cur[i][1]>r-k+1) {
res--;
}
}
i++;
}
i = old;
continue;
} else {
res += (int)(b1[id].size());
assert((int)b1[id].size() == (int)b2[id].size());
int tl = 0, tr = (int)b1[id].size()-1, x1 = 0, x2 = 0;
while(tl<=tr) {
int mid = (tl+tr)/2;
if(b1[id][mid]>r-k+1) {
x1 = mid+1;
tl = mid+1;
} else {
tr = mid-1;
}
}
res -= x1;
tl = 0, tr = (int)b2[id].size()-1;
while(tl<=tr) {
int mid = (tl+tr)/2;
if(b2[id][mid]<l+k-1) {
x2 = mid+1;
tl = mid+1;
} else {
tr = mid-1;
}
}
res -= x2;
}
}
for(auto [c, d, x] : add) {
int len = min(d, r)-max(l, c)+1;
if(len >= k) {
res += x;
}
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> t;
int ans = 0, timer = 0;
for(int i = 1; i <= n; ++i) {
char tp;
cin >> tp;
if(tp == '1') {
int l, r;
cin >> l >> r;
l = (l^(t*ans));
r = (r^(t*ans));
if(l>r) {
swap(l, r);
}
a[++timer] = {l, r};
add.push_back({l, r, 1});
active.insert({l, r});
} else if(tp == '2') {
int id;
cin >> id;
add.push_back({a[id].first, a[id].second, -1});
auto it = active.find(a[id]);
active.erase(it);
} else {
int l, r, k;
cin >> l >> r >> k;
l = (l^(t*ans));
r = (r^(t*ans));
if(l>r) {
swap(l, r);
}
if(r-l+1<k) {
cout << (ans=0) << "\n";
continue;
}
cout << (ans = get(l, r, k)) << "\n";
}
if((int)add.size()>K) {
build();
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
758 ms |
6300 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
2088 KB |
Output is correct |
2 |
Correct |
41 ms |
1932 KB |
Output is correct |
3 |
Correct |
47 ms |
2192 KB |
Output is correct |
4 |
Correct |
40 ms |
2132 KB |
Output is correct |
5 |
Correct |
1203 ms |
8004 KB |
Output is correct |
6 |
Correct |
978 ms |
6688 KB |
Output is correct |
7 |
Correct |
1080 ms |
6860 KB |
Output is correct |
8 |
Correct |
1625 ms |
8740 KB |
Output is correct |
9 |
Correct |
1701 ms |
8716 KB |
Output is correct |
10 |
Correct |
1348 ms |
6860 KB |
Output is correct |
11 |
Correct |
125 ms |
2372 KB |
Output is correct |
12 |
Correct |
1387 ms |
7440 KB |
Output is correct |
13 |
Correct |
1208 ms |
6168 KB |
Output is correct |
14 |
Correct |
675 ms |
4324 KB |
Output is correct |
15 |
Correct |
573 ms |
3724 KB |
Output is correct |
16 |
Correct |
399 ms |
3272 KB |
Output is correct |
17 |
Correct |
802 ms |
5948 KB |
Output is correct |
18 |
Correct |
803 ms |
5896 KB |
Output is correct |
19 |
Correct |
821 ms |
6004 KB |
Output is correct |
20 |
Correct |
809 ms |
5852 KB |
Output is correct |
21 |
Correct |
178 ms |
2432 KB |
Output is correct |
22 |
Correct |
848 ms |
4812 KB |
Output is correct |
23 |
Correct |
1087 ms |
5608 KB |
Output is correct |
24 |
Correct |
927 ms |
4952 KB |
Output is correct |
25 |
Correct |
44 ms |
2152 KB |
Output is correct |
26 |
Correct |
38 ms |
2052 KB |
Output is correct |
27 |
Correct |
42 ms |
2068 KB |
Output is correct |
28 |
Correct |
41 ms |
2036 KB |
Output is correct |
29 |
Correct |
1218 ms |
5900 KB |
Output is correct |
30 |
Correct |
1230 ms |
6108 KB |
Output is correct |
31 |
Correct |
1711 ms |
8600 KB |
Output is correct |
32 |
Correct |
1387 ms |
6768 KB |
Output is correct |
33 |
Correct |
1243 ms |
6404 KB |
Output is correct |
34 |
Correct |
602 ms |
3772 KB |
Output is correct |
35 |
Correct |
1059 ms |
5524 KB |
Output is correct |
36 |
Correct |
1292 ms |
6896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
39 ms |
2032 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |