//https://oj.uz/problem/view/IZhO18_segments
#include<bits/stdc++.h>
const int N = 2e5 + 5;
const int MAGIC = 1001;
using namespace std;
struct segment{
int l, r, id;
};
vector <segment> mv;
int n, t, L[N], R[N], ans, cnt, cur;
int l_sort[N], r_sort[N], l_nosort[N], r_nosort[N], p[N], num;
bool ck[N];
int bsearch(int l, int r, int k){
while (l != r){
int mid = (l + r) >> 1;
if (r_nosort[mid] - l_nosort[mid] + 1 >= k) r = mid;
else l = mid + 1;
}
if (r_nosort[l] - l_nosort[l] + 1 < k) return l + 1;
return l;
}
void get_L(int pos, int k){
int Max = (pos / MAGIC + 1) * MAGIC;
for (int i = pos; i < min(Max, cnt); i++) if (r_nosort[pos] < k) ans--;
for (int i = Max; i < cnt; i += MAGIC){
int x = i, y = min(i + MAGIC, cnt);
int val = lower_bound(r_sort+x, r_sort+y, k) - r_sort - x;
ans -= val;
}
}
void get_R(int pos, int k){
int Max = (pos / MAGIC + 1) * MAGIC;
for (int i = pos; i < min(Max, cnt); i++) if (l_nosort[pos] > k) ans--;
for (int i = Max; i < cnt; i += MAGIC){
int x = i, y = min(i + MAGIC, cnt);
int val = y - (upper_bound(l_sort+x, l_sort+y, k) - l_sort);
ans -= val;
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> t;
if (n > 5000) return 0;
while (n--){
if (mv.size() == 1){
cnt = 0; mv.clear();
for (int i = 1; i < N; i++) if (ck[i]) p[cnt++] = i;
sort(p, p+cnt, [](int x, int y){return (R[x] - L[x]) < (R[y] - L[y]);});
for (int i = 0; i < cnt; i++) l_sort[i] = l_nosort[i] = L[p[i]];
for (int i = 0; i < cnt; i++) r_sort[i] = r_nosort[i] = R[p[i]];
for (int i = 0; i < cnt; i += MAGIC){
int x = i, y = min(i + MAGIC, cnt);
sort(l_sort+x, l_sort+y);
sort(r_sort+x, r_sort+y);
}
}
int type, l, r, id, k;
cin >> type;
if (type == 1){
num++; id = ++cur;
cin >> l >> r;
l ^= (t * ans); r ^= (t * ans); if (r < l) swap(l, r);
ck[id] = true;
L[id] = l; R[id] = r;
mv.push_back({l, r, 1});
}
if (type == 2){
num--;
cin >> id;
ck[id] = false;
mv.push_back({L[id], R[id], -1});
}
if (type == 3){
cin >> l >> r >> k;
l ^= (t * ans); r ^= (t * ans); if (r < l) swap(l, r);
if (r - l + 1 < k){
ans = 0; cout << ans << "\n";
continue;
}
ans = num;
if (cnt > 0){
int pos = bsearch(0, cnt-1, k);
ans -= pos;
get_L(pos, l + k - 1);
get_R(pos, r - k + 1);
}
for (int i = 0; i < mv.size(); i++){
int x = max(mv[i].l, l), y = min(mv[i].r, r);
if (y - x + 1 < k) ans -= mv[i].id;
}
cout << ans << "\n";
}
}
}
Compilation message
segments.cpp: In function 'int main()':
segments.cpp:94:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < mv.size(); i++){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
658 ms |
684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
658 ms |
684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
658 ms |
684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
