Submission #919588

#TimeUsernameProblemLanguageResultExecution timeMemory
919588Khanhcsp2Monkey and Apple-trees (IZhO12_apple)C++14
100 / 100
384 ms207984 KiB
#include <bits/stdc++.h> #define el '\n' #define fi first #define sc second #define int ll #define pii pair<int, int> #define all(v) v.begin(), v.end() using namespace std; using ll=long long; using ull=unsigned long long; using ld=long double; const int mod=1e9+7; const int N=1e5+11; int q; struct node { int sum, lazy; node* l; node* r; node() { l=r=NULL; sum=lazy=0; } }; node* root; void down(node* pos, int l, int r) { if(pos->lazy==0) return; int mid=(l+r)>>1; pos->l->lazy=pos->lazy; pos->r->lazy=pos->lazy; pos->l->sum=(pos->lazy)*(mid-l+1); pos->r->sum=(pos->lazy)*(r-mid); } void update(node* pos, int l, int r, int u, int v, int val) { if(l>v||r<u) return; if(u<=l && r<=v) { pos->sum=val*(r-l+1); pos->lazy=val; return; } if(pos->l==NULL) pos->l = new node(); if(pos->r==NULL) pos->r = new node(); int mid=(l+r)>>1; down(pos, l, r); update(pos->l, l, mid, u, v, val); update(pos->r, mid+1, r, u, v, val); pos->sum=pos->l->sum+pos->r->sum; } int get(node* pos, int l, int r, int u, int v) { if(l>v||r<u) return 0; if(u<=l && r<=v) { return pos->sum; } if(pos->l==NULL) pos->l = new node(); if(pos->r==NULL) pos->r = new node(); down(pos, l, r); int mid=(l+r)>>1; return get(pos->l, l, mid, u, v)+get(pos->r, mid+1, r, u, v); } void sol() { cin >> q; int c=0; root = new node(); while(q--) { int tt, x, y; cin >> tt >> x >> y; x+=c; y+=c; if(tt==1) { int ans=get(root, 1, 1e9, x, y); c=ans; cout << ans << el; } else { update(root, 1, 1e9, x, y, 1); } } } signed main() { // freopen("divisor.INP", "r", stdin); // freopen("divisor.OUT", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int t=1; //cin >> t; while(t--) { sol(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...