#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const llint off = 1LL << 32;
const int maxn = 2e5+10;
struct node {
int val;
node *l, *r;
node() {
val = 0;
l = r = nullptr;
}
};
typedef node* pnode;
int value(pnode tren) {
if (tren == nullptr) return 0;
return tren->val;
}
pnode L(pnode tren) {
if (tren == nullptr) return nullptr;
return tren->l;
}
pnode R(pnode tren) {
if (tren == nullptr) return nullptr;
return tren->r;
}
int n, t;
set< int > s;
pnode lef, rig;
pair<llint, llint> niz[maxn];
void update(llint x, llint l, llint r, pnode tren, int val) {
//printf("update: %lld %lld %lld %d %d\n", x, l, r, tren, val);
if (x < l || x > r) return;
if (l == r) {
tren->val += val;
return;
}
int mid = (l + r) / 2;
if (x <= mid) {
if (tren->l == nullptr) tren->l = new node();
update(x, l, mid, tren->l, val);
} else {
if (tren->r == nullptr) tren->r = new node();
update(x, mid + 1, r, tren->r, val);
}
tren->val = value(tren->l) + value(tren->r);
}
int query(llint a, llint b, llint l, llint r, pnode node) {
if (l > b || r < a) return 0;
if (node == nullptr) return 0;
if (l >= a && r <= b) return value(node);
int mid = (l + r) / 2;
return query(a, b, l, mid, node->l) + query(a, b, mid + 1, r, node->r);
}
int main() {
scanf("%d%d", &n, &t);
for (int i = 1; i <= n + 2; i++)
s.insert(i);
//printf("off: %lld\n", off);
int lastans = 0;
lef = new node();
rig = new node();
int cnt = 0;
while (n--) {
int type;
scanf("%d", &type);
if (type == 1) {
llint l, r;
scanf("%lld%lld", &l, &r);
l = l ^ (t * lastans);
r = r ^ (t * lastans);
if (l > r) swap(l, r);
int ind = *s.begin();
s.erase(s.begin()); cnt++;
update(r, 0, off - 1, lef, 1);
update(l, 0, off - 1, rig, 1);
niz[ind] = {l, r};
} else if (type == 2) {
int id;
scanf("%d", &id);
llint l = niz[id].X, r = niz[id].Y;
update(r, 0, off - 1, lef, -1);
update(l, 0, off - 1, rig, -1);
s.insert(id); cnt--;
} else {
llint l, r, k;
scanf("%lld%lld%lld", &l, &r, &k);
l = l ^ (t * lastans); l--;
r = r ^ (t * lastans); r++;
if (l > r) swap(l, r);
lastans = cnt;
lastans -= query(0, l, 0, off - 1, lef);
lastans -= query(r, off - 1, 0, off - 1, rig);
printf("%d\n", lastans);
}
}
return 0;
}
Compilation message
segments.cpp: In function 'int main()':
segments.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d%d", &n, &t);
| ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d", &type);
| ~~~~~^~~~~~~~~~~~~
segments.cpp:84:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%lld%lld", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
segments.cpp:97:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d", &id);
| ~~~~~^~~~~~~~~~~
segments.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | scanf("%lld%lld%lld", &l, &r, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
178 ms |
53680 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
38804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
148 ms |
39060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
