#include <bits/stdc++.h>
using namespace std;
#define print(arr) for(auto& x:arr)cout<<x<<" ";cout<<"\n"
#define watch(x) cout<<#x<<"="<<x<<"\n"
#define all(x) x.begin(), x.end()
#define sz(x) ((int) x.size())
#define PB push_back
#define S second
#define F first
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
ll oper(ll x, ll y){
return x+y;
}
struct Node {
ll lz, lzL, lzR, val;
Node *L, *R;
Node(ll lz = 0) : lz(lz), lzL(0), lzR(0), val(0), L(0), R(0) {}
void propagate(ll l, ll r) {
if(lz) {
if(l != r) {
if(L) L->lz = 1;
else lzL = 1;
if(R) R->lz = 1;
else lzR = 1;
}
val = (r-l+1)*lz;
lz = 0;
}
}
};
ll null = 0;
ll get_val(Node* root, ll lz, ll a, ll b) {
if(!root) return lz*(b-a+1);
return root->val;
}
struct SegTree {
Node* root;
ll n;
SegTree(ll n) : n(n), root(new Node()) {}
void update(Node* &root, ll a, ll b, ll l, ll r, ll x, ll lz = 0) {
if((l > b || r < a) && !root) return; // break condition, this line optimizes memory
if(root == nullptr) root = new Node(lz);
root->propagate(l, r);
if(l > b || r < a) return;
if(a <= l && r <= b) {
root->lz = oper(root->lz, x);
root->propagate(l, r);
} else {
ll m = (l+r) >> 1;
update(root->L, a, b, l, m, x, root->lzL);
update(root->R, a, b, m+1, r, x, root->lzR);
root->val = oper(get_val(root->L, root->lzL, l, m),get_val(root->R, root->lzR, m+1, r));
}
}
ll get(Node* root, ll a, ll b, ll l, ll r, ll lz = 0) {
if(l > b || r < a) return null;
if(root) root->propagate(l, r);
if((a <= l && r <= b) || !root) {
return get_val(root, lz, l, r);
} else {
ll m = (l+r) >> 1;
return oper(get(root->L, a, b, l, m, root->lzL), get(root->R, a, b, m+1, r, root->lzR));
}
}
void update(ll a, ll b, ll x) { update(root, a, b, 0, n-1, x); }
ll get(ll a, ll b) { return get(root, a, b, 0, n-1); }
};
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
SegTree st(1e9);
ll q;cin>>q;
ll op,l,r,c=0;
while(q--){
cin>>op>>l>>r;
l--;r--;
if(op==1){
c=st.get(l+c,r+c);
cout<<c<<"\n";
}else{
st.update(l+c,r+c,1);
}
}
return 0;
}
Compilation message
apple.cpp: In constructor 'SegTree::SegTree(ll)':
apple.cpp:46:5: warning: 'SegTree::n' will be initialized after [-Wreorder]
46 | ll n;
| ^
apple.cpp:45:8: warning: 'Node* SegTree::root' [-Wreorder]
45 | Node* root;
| ^~~~
apple.cpp:47:2: warning: when initialized here [-Wreorder]
47 | SegTree(ll n) : n(n), root(new Node()) {}
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
