#include<bits/stdc++.h>
using namespace std;
const int N = (1 << 17);
struct tree {
vector<int> st[2 * N];
int sz = 0;
void init(vector<int> &a) {
sz = (int)a.size();
build(a, 0, sz - 1, 1);
}
void build(vector<int> &a, int l, int r, int v) {
if(l == r) {
st[v].push_back(a[l]);
return;
}
int m = (l + r) / 2;
build(a, l, m, 2 * v);
build(a, m + 1, r, 2 * v + 1);
int lb = 0, rb = 0;
while(lb < (int)st[2 * v].size() || rb < (int)st[2 * v + 1].size()) {
int val1 = 2e9 + 1, val2 = 2e9 + 1;
if(lb < (int)st[2 * v].size()) val1 = st[2 * v][lb];
if(rb < (int)st[2 * v + 1].size()) val2 = st[2 * v + 1][rb];
if(val1 < val2) st[v].push_back(st[2 * v][lb++]);
else st[v].push_back(st[2 * v + 1][rb++]);
}
}
int get(int ql, int qr, int x, int l, int r, int v) {
if(ql > qr || r < ql || l > qr)
return 0;
if(ql <= l && r <= qr) {
int lb = -1, rb = (int)st[v].size();
while(rb - lb > 1) {
int m = (lb + rb) / 2;
if(st[v][m] < x) lb = m;
else rb = m;
}
return lb + 1;
}
int m = (l + r) / 2;
return get(ql, qr, x, l, m, 2 * v) + get(ql, qr, x, m + 1, r, 2 * v + 1);
}
int get(int ql, int qr, int x) {
return get(ql, qr, x, 0, sz - 1, 1);
}
};
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 a, b;
cin >> a >> b;
if(a > b) swap(a, b);
v.push_back({a, b});
} 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 += (int)v.size() - rb;
lastans -= t1.sz - t1.get(rb, (int)v.size() - 1, r - k + 2);
lastans -= t2.get(rb, (int)v.size() - 1, l + k - 1);
cout << lastans << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
237 ms |
26504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
13132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
13108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
