// 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.fi, b.se - a.fi) + 1);}
inline int findLess(vector<int> &v, int x) {return lower_bound(v.begin(), v.end(), x) - v.begin();}
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 < saved.size(); i++) {
left[ptr].push_back(saved[i].fi);
right[ptr].push_back(saved[i].se);
if (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 (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 < left.size(); st += left[i].size(), i++) {
if (len[st + 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 + left[i].size(); j++) {
if (intersect(segment, saved[j])) {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 = sqrt(n);
DelayedVector All, Deleted;
for (int typ, a, b, k, id, i = 1; i <= n; i++) {
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);
} else if (typ == 2) {
scanf("%d", &id);
Deleted.update(segments[id].fi, segments[id].se);
} 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);
}
//All.print();
//Deleted.print();
}
}
Compilation message
segments.cpp: In member function 'void DelayedVector::rebuild()':
segments.cpp:46:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int ptr = 0, i = 0; i < saved.size(); i++) {
| ~~^~~~~~~~~~~~~~
segments.cpp:50:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
50 | if (left[ptr].size() >= sqrtn) {
| ~~~~~~~~~~~~~~~~~^~~~~~~~
segments.cpp: In member function 'void DelayedVector::update(int, int)':
segments.cpp:66:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
66 | if (pending.size() > sqrtn) {rebuild();}
| ~~~~~~~~~~~~~~~^~~~~~~
segments.cpp: In member function 'int DelayedVector::query(int, int, int)':
segments.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i = 0; i < left.size(); st += left[i].size(), i++) {
| ~~^~~~~~~~~~~~~
segments.cpp:91:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int j = st; j < st + left[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | scanf("%d %d", &n, &t);
| ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | scanf("%d", &typ);
| ~~~~~^~~~~~~~~~~~
segments.cpp:137:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:146:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
146 | scanf("%d", &id);
| ~~~~~^~~~~~~~~~~
segments.cpp:151:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
151 | scanf("%d %d %d", &a, &b, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
572 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
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 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
