Submission #1240709

#TimeUsernameProblemLanguageResultExecution timeMemory
1240709MalixMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
1 ms324 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<int,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) #define all(x) (x).begin(),(x).end() ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; struct Node{ int val,lazy,p,q; Node *l,*r; Node(int x,int y,int z):val(x),lazy(0),p(y),q(z),l(NULL),r(NULL){} }*root; void push(Node *&x){ int m=(x->p+x->q)/2; if(x->l){ x->l->val=m-x->p+1; x->l->lazy=1; } else x->l=new Node(m-x->p+1,x->p,m); if(x->r){ x->r->val=x->q-m; x->r->lazy=1; } else x->r=new Node(x->q-m,m+1,x->q); x->lazy=0; } void update(Node *&x,int l,int r,int u,int v){ if(u>v)return; if(!x)x=new Node(0,l,r); if(l!=r&&x->lazy)push(x); if(l==u&&r==v){ x->val=r-l+1; x->lazy=1; return; } int m=(l+r)/2; update(x->l,l,m,u,min(m,v)); update(x->r,m+1,r,max(m+1,u),v); x->val=(x->l?x->l->val:0)+(x->r?x->r->val:0); } int query(Node *&x,int l,int r,int u,int v){ if(u>v||!x)return 0; if(l!=r&&x->lazy)push(x); if(l==u&&r==v)return x->val; int m=(l+r)/2; return query(x->l,l,m,u,min(m,v))+query(x->r,m+1,r,max(m+1,u),v); } int main(){ ios::sync_with_stdio(0); cin.tie(0); int c=0; int q;cin>>q; root=new Node(0,1,inf); while(q--){ int t,x,y;cin>>t>>x>>y; x+=c;y+=c; if(t==2)update(root,1,inf,x,y); else{ c=query(root,1,inf,x,y); cout<<c<<"\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...