#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Node {
int ans, lazy, tl, tr, l, r; //lzset
Node() : ans(0), lazy(0), l(-1), r(-1) {}
};
#define MAXN 100009
Node st[32 * MAXN];
int cnt = 2; //scuffed coord compression
void push_lazy(int node) {
if (st[node].lazy !=0) { //there is shit to lazy set
st[node].ans = st[node].tr - st[node].tl + 1; // amount set in this interval isj ust size of interval
int mid = (st[node].tl + st[node].tr) / 2;
if (st[node].l == -1) { // if no left child, create one (yay)
st[node].l = cnt++; //create left child
st[st[node].l].tl = st[node].tl; //left child "border" is same as cur node's border
st[st[node].l].tr = mid;
}
if (st[node].r == -1) { //same shit for right child
st[node].r = cnt++; //create right child
st[st[node].r].tl = mid + 1;
st[st[node].r].tr = st[node].tr;
}
st[st[node].l].lazy = st[st[node].r].lazy = 1; //lzset both children
st[node].lazy = 0;
}
}
void update(int node, int l, int r) {
push_lazy(node); //update/create children
if (l == st[node].tl && r == st[node].tr) { //if we're fully in a node
st[node].lazy = 1; //set lzset to 1
push_lazy(node); // no idea why this is here but taking it out breaks the code
// never mind i figured out why line above is there lmfao
} else {
int mid = (st[node].tl + st[node].tr) / 2;
if (st[node].l == -1) { //same shit again i guess- create children if children weren't there before
st[node].l = cnt++;
st[st[node].l].tl = st[node].tl;
st[st[node].l].tr = mid;
}
if (st[node].r == -1) { //same thing; create children
st[node].r = cnt++;
st[st[node].r].tl = mid + 1;
st[st[node].r].tr = st[node].tr;
}
if (l > mid) update(st[node].r, l, r); //see where we are, do updates on children depending on where median is
else if (r <= mid) update(st[node].l, l, r);
else {
update(st[node].l, l, mid);
update(st[node].r, mid + 1, r);
}
push_lazy(st[node].l); // no clue why this line or nextl ine is here reeeee
push_lazy(st[node].r);
st[node].ans = st[st[node].l].ans + st[st[node].r].ans; // answer is sum of segments, ans stored in st[node].ans
}
}
int query(int node, int l, int r) {
push_lazy(node);
if (l == st[node].tl && r == st[node].tr) return st[node].ans;
else {
int mid = (st[node].tl + st[node].tr) / 2; // WHY DO WE DO THE SAME SHIT AS PUSH_LAZY
if (st[node].l == -1) {
st[node].l = cnt++;
st[st[node].l].tl = st[node].tl;
st[st[node].l].tr = mid;
}
if (st[node].r == -1) {
st[node].r = cnt++;
st[st[node].r].tl = mid + 1;
st[st[node].r].tr = st[node].tr;
}
if (l > mid) return query(st[node].r, l, r); //see where mid lies wrt l, r and qry accordingly
else if (r <= mid) return query(st[node].l, l, r);
else return query(st[node].l, l, mid) + query(st[node].r, mid + 1, r);
}
}
int32_t main() {
iostream::sync_with_stdio(false);
cin.tie(0);
int m;
cin >> m;
st[1].ans = 0; st[1].lazy = 0; //yay initialize shit
st[1].tl = 1; st[1].tr = 1e9;
int c = 0;
for(int i=0; i<m; i++) {
int d, x, y;
cin >> d >> x >> y;
if (d == 1) {
c = query(1, x + c, y + c);
cout << c << '\n';
} else update(1, x + c, y + c);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
150604 KB |
Output is correct |
| 2 |
Correct |
56 ms |
150580 KB |
Output is correct |
| 3 |
Correct |
57 ms |
150528 KB |
Output is correct |
| 4 |
Correct |
68 ms |
150732 KB |
Output is correct |
| 5 |
Correct |
76 ms |
150708 KB |
Output is correct |
| 6 |
Correct |
68 ms |
150792 KB |
Output is correct |
| 7 |
Correct |
70 ms |
150760 KB |
Output is correct |
| 8 |
Correct |
166 ms |
151636 KB |
Output is correct |
| 9 |
Correct |
313 ms |
152768 KB |
Output is correct |
| 10 |
Correct |
301 ms |
152668 KB |
Output is correct |
| 11 |
Runtime error |
440 ms |
262144 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
