#include<bits/stdc++.h>
using namespace std;
#define all(c) begin(c), end(c)
#define rep(ind, st, end) for(int ind = st;ind<end; ind++)
#define ssize(c) static_cast<int>(c.size())
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define vv vector<vector
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using pll = pair<ll, ll>;
using vvpii = vector<vector<pii>>;
struct PersistentST
{
using Value = ll;
using Update = ll;
ll inf = 1e17;
Value unit = Value(0);
static const Update no_update = Update{0}; // null update
Value merge(Value a, Value b) { return a + b; }
struct Vertex {
Value val;
ll l = -1, r = -1;
Update upd = no_update;
Vertex(Value v, ll _sx, ll _dx) : val(v), l(_sx), r(_dx) {}
Vertex(Value v) : val(v) {}
};
void update_node(Vertex& a, Update upd, ll l, ll r) {
a.val = upd * (r - l + 1);
}
Update combine_updates(Update prev, Update upd) {
return upd;
}
int n;
vector<Vertex> st{Vertex{unit}};
PersistentST(const vector<pair<ll, Value>>& data) {
n = data.size();
for(auto [ind, val]:data)
update(ind, ind, val);
}
void push(int u, ll l, ll r) {
if(l == r) return;
//cout <<"l and r of pos "<<u<<" are "<<st[u].l<<' '<<st[u].r<<endl;
if(st[u].l == -1) {
st[u].l = ssize(st);
//cout<<"Created st["<<u<<"].l = "<<st[u].l<<endl;
st.push_back(Vertex(unit));
}
if(st[u].r == -1) {
st[u].r = ssize(st);
//cout<<"Created st["<<u<<"].r = "<<st[u].r<<endl;
st.push_back(Vertex(unit));
}
if(st[u].upd != no_update) {
//cout<<"CALL UPD_N ON "<<st[u].l<<endl;
update_node(st[st[u].l], st[u].upd, l, (l+r)/2);
//cout<<"CALL UPD_N ON "<<st[u].r<<endl;
update_node(st[st[u].r], st[u].upd, (l+r)/2+1, r);
if(l < r) {
st[st[u].l].upd = combine_updates(st[st[u].l].upd, st[u].upd);
st[st[u].r].upd = combine_updates(st[st[u].r].upd, st[u].upd);
}
st[u].upd = no_update;
}
}
void update(int u, ll l, ll r, ll x, ll y, Update v) {
//cout<<l<<' '<<r<<endl;
if(r < x || y < l) return;
if(x <= l && r <= y) {
//cout<<"IM IN "<<x<<' '<<y<<' '<<l<<' '<<r<<'\n'<<u<<endl;
update_node(st[u], v, l, r);
if(l != r)
st[u].upd = combine_updates(st[u].upd, v);
}
else {
push(u, l, r);
update(st[u].l, l, (l+r)/2, x, y, v);
update(st[u].r, (l+r)/2+1, r, x, y, v);
st[u].val = merge(st[st[u].l].val, st[st[u].r].val);
}
}
Value query(int u, ll l, ll r, ll x, ll y) {
//cout<<"sto a "<<l <<' '<<r<<' '<<st[u].val<<' '<<st[u].upd<<" dpt = "<<dpt<<endl;
if(r < x || l > y) return unit;
if(l >= x && r <= y)
{
//cout<<"queried value "<<st[u].val<<" at pos "<<u<<" covering interval "<<l<<" - "<<r<<endl;
return st[u].val;
}
push(u, l, r);
return merge(
query(st[u].l, l, (l+r)/2, x, y),
query(st[u].r, (l+r)/2+1, r, x, y)
);
}
// [x, y]
Value query(ll x, ll y) { return query(0, 0, inf, x, y); }
void update(ll x, ll y, Update v) { update(0, 0, inf, x, y, v); }
};
int main() {
iostream::sync_with_stdio(false);
cin.tie(0);
int m;
cin >> m;
PersistentST st({});
int c = 0;
rep(i, 0, m) {
int d, x, y;
cin >> d >> x >> y;
if (d == 1) {
c = st.query(x + c, y + c);
cout << c << '\n';
} else st.update(x + c, y + c, 1);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
15 ms |
4724 KB |
Output is correct |
| 5 |
Correct |
18 ms |
4664 KB |
Output is correct |
| 6 |
Correct |
17 ms |
4684 KB |
Output is correct |
| 7 |
Correct |
17 ms |
4672 KB |
Output is correct |
| 8 |
Correct |
134 ms |
33804 KB |
Output is correct |
| 9 |
Correct |
247 ms |
66620 KB |
Output is correct |
| 10 |
Correct |
258 ms |
66772 KB |
Output is correct |
| 11 |
Correct |
266 ms |
66416 KB |
Output is correct |
| 12 |
Correct |
266 ms |
66684 KB |
Output is correct |
| 13 |
Correct |
269 ms |
132940 KB |
Output is correct |
| 14 |
Correct |
270 ms |
132852 KB |
Output is correct |
| 15 |
Runtime error |
407 ms |
262144 KB |
Execution killed with signal 9 |
| 16 |
Halted |
0 ms |
0 KB |
- |
