// I am now here, but I have yet to prove that I am worthy of my place here.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second
int n, t, lastans;
vector<pii> segments(1);
int sqrtn;
inline const bool comp(const pii &a,const pii &b) {return ((a.se - a.fi) > (b.se - b.fi));}
inline int intersect(pii a, pii b) {
return max(0, min(a.se, b.se) - max(a.fi, b.fi) + 1);
}
inline int findLess(vector<int> &v, int x) {return lower_bound(v.begin(), v.end(), x) - v.begin();}
#define assert_WA(x) if (!(x)) printf("!!!\n")
struct DelayedVector {
vector<pii> pending, saved;
vector<int> len;
vector<vector<int>> left, right;
DelayedVector() {}
void rebuild() {
sort(pending.begin(), pending.end(), comp);
auto F = saved.begin();
auto M = saved.end();
auto L = saved.end() + pending.size();
for (auto &i : pending) {saved.push_back(i);}
pending.clear();
inplace_merge(F, M, L, comp);
// recompute lengths
len.clear();
for (auto &[l, r] : saved) {len.push_back(r - l + 1);}
// recompute blocks
left.clear(); right.clear();
left.push_back({}); right.push_back({});
for (int ptr = 0, i = 0; i < (int)saved.size(); i++) {
left[ptr].push_back(saved[i].fi);
right[ptr].push_back(saved[i].se);
if ((int)left[ptr].size() >= sqrtn) {
ptr++;
left.push_back({}); right.push_back({});
}
}
if (left.back().empty()) {left.pop_back();}
if (right.back().empty()) {right.pop_back();}
for (auto &i : left) {sort(i.begin(), i.end());}
for (auto &i : right) {sort(i.begin(), i.end());}
}
void update(int l, int r) {
pending.push_back({l, r});
// rebuild the sqrt decomposition
if ((int)pending.size() > sqrtn) {rebuild();}
}
int query(int k, int l, int r) {
// a segment [x, y] does not have at least k points in common with [l, r] if
// x > (r - (k - 1)) || y < (l + (k - 1))
if (k > (r - l + 1)) return 0;
int ans = 0;
pii segment = {l, r};
for (auto &p : pending) {
if (intersect(segment, p) >= k) {ans++;}
}
int st = 0;
for (int i = 0; i < (int)left.size(); st += (int)left[i].size(), i++) {
assert_WA(st < (int)saved.size());
assert_WA(st + (int)left[i].size() - 1 < (int)saved.size());
if (len[st + (int)left[i].size() - 1] >= k) {
ans += findLess(left[i], r - (k-1) + 1);
//cout << ans << '\n';
ans -= findLess(right[i], l + (k-1));
//cout << l + (k-1) << ' ' << ans << '\n';
} else if (len[st] >= k) {
for (int j = st; j < st + (int)left[i].size(); j++) {
if (intersect(segment, saved[j]) >= k) {ans++;}
}
} else break;
}
return ans;
}
void print() {
printf("Pending: ");
for (auto &[l, r] : pending) {printf("[%d, %d] ", l, r);}
printf("\n");
printf("Saved: ");
for (auto &[l, r] : saved) {printf("[%d, %d] ", l, r);}
printf("\n");
printf("Left: ");
for (auto &i : left) {
printf("[ ");
for (auto &j : i) {printf("%d ", j);}
printf("] ");
}
printf("\n");
printf("Right: ");
for (auto &i : right) {
printf("[ ");
for (auto &j : i) {printf("%d ", j);}
printf("] ");
}
printf("\n\n");
}
};
int main() {
scanf("%d %d", &n, &t);
sqrtn = 1000;//sqrt(n);
DelayedVector All, Deleted;
for (int typ, a, b, k, id, i = 1; i <= n; i++) {
//cerr << i << '\n';
scanf("%d", &typ);
if (typ == 1) {
scanf("%d %d", &a, &b);
a ^= (t * lastans);
b ^= (t * lastans);
if (a > b) {swap(a, b);}
segments.push_back({a, b});
All.update(a, b);
//cerr << i << ' ' << a << ' ' << b << '\n';
} else if (typ == 2) {
scanf("%d", &id);
assert(id < segments.size());
Deleted.update(segments[id].fi, segments[id].se);
//cerr << i << ' ' << id << '\n';
} else {
scanf("%d %d %d", &a, &b, &k);
a ^= (t * lastans);
b ^= (t * lastans);
if (a > b) {swap(a, b);}
lastans = All.query(k, a, b) - Deleted.query(k, a, b);
printf("%d\n", lastans);
//cerr << i << ' ' << a << ' ' << b << ' ' << k << '\n';
}
//All.print();
//Deleted.print();
}
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from segments.cpp:3:
segments.cpp: In function 'int main()':
segments.cpp:159:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | assert(id < segments.size());
| ~~~^~~~~~~~~~~~~~~~~
segments.cpp:138:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | scanf("%d %d", &n, &t);
| ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | scanf("%d", &typ);
| ~~~~~^~~~~~~~~~~~
segments.cpp:147:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:158:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | scanf("%d", &id);
| ~~~~~^~~~~~~~~~~
segments.cpp:166:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | scanf("%d %d %d", &a, &b, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
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 |
7 ms |
340 KB |
Output is correct |
| 4 |
Correct |
7 ms |
496 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
656 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
656 KB |
Execution killed with signal 11 |
| 2 |
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 |
7 ms |
340 KB |
Output is correct |
| 4 |
Correct |
7 ms |
496 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 6 |
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 |
7 ms |
340 KB |
Output is correct |
| 4 |
Correct |
7 ms |
496 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
