#include<bits/stdc++.h>
using namespace std;
const int N = (1 << 17);
const int B = 317;
struct tree {
vector<int> st[N / B + 10];
vector<int> a;
int sz = 0;
void init(vector<int> &a) {
this->a = a;
sz = (int)a.size();
build();
}
void build() {
for(int i = 0; i < sz; i++) {
st[i / B].push_back(a[i]);
}
for(int i = 0; i <= (sz - 1) / B; i++)
sort(st[i].begin(), st[i].end());
}
int get(int ql, int qr, int x) {
int ans = 0;
while(ql <= qr) {
bool f = (ql % B == 0 && ql + B - 1 <= qr);
if(f) {
int lb = -1, rb = (int)st[ql / B].size();
while(rb - lb > 1) {
int m = (lb + rb) / 2;
if(st[ql / B][m] < x) lb = m;
else rb = m;
}
ans += lb + 1;
ql += B;
} else {
ans += (a[ql] < x);
ql++;
}
}
return ans;
}
};
vector<pair<int, int>> v;
// left bounds, right bounds
vector<int> ll, rr;
tree t1, t2;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n, t;
cin >> n >> t;
int lastans = 0;
bool isBuilt = 0;
for(int i = 1; i <= n; i++) {
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});
} else {
if(!isBuilt) {
sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b){return a.second - a.first < b.second - b.first;});
for(int i = 0; i < (int)v.size(); i++) {
ll.push_back(v[i].first);
rr.push_back(v[i].second);
}
t1.init(ll);
t2.init(rr);
isBuilt = 1;
}
int l, r, k;
cin >> l >> r >> k;
l = (l ^ (t * lastans));
r = (r ^ (t * lastans));
lastans = 0;
if(l > r) swap(l, r);
if(r - l + 1 < k) {
cout << 0 << '\n';
continue;
}
int lb = -1, rb = (int)v.size();
while(rb - lb > 1) {
int m = (lb + rb) / 2;
if(v[m].second - v[m].first + 1 >= k) rb = m;
else lb = m;
}
lastans = t1.get(rb, (int)v.size() - 1, r - k + 2) - t2.get(rb, (int)v.size() - 1, l + k - 1);
cout << lastans << '\n';
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
709 ms |
2440 KB |
Output is correct |
2 |
Correct |
679 ms |
2416 KB |
Output is correct |
3 |
Correct |
705 ms |
2320 KB |
Output is correct |
4 |
Correct |
677 ms |
2584 KB |
Output is correct |
5 |
Correct |
192 ms |
4020 KB |
Output is correct |
6 |
Correct |
134 ms |
6172 KB |
Output is correct |
7 |
Correct |
692 ms |
5052 KB |
Output is correct |
8 |
Correct |
696 ms |
5308 KB |
Output is correct |
9 |
Correct |
675 ms |
5072 KB |
Output is correct |
10 |
Correct |
498 ms |
4464 KB |
Output is correct |
11 |
Correct |
555 ms |
4616 KB |
Output is correct |
12 |
Correct |
632 ms |
5796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
69 ms |
788 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
75 ms |
780 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |