Submission #848945

#TimeUsernameProblemLanguageResultExecution timeMemory
848945Ahmed_SolymanMonkey and Apple-trees (IZhO12_apple)C++14
0 / 100
2346 ms262144 KiB
/* In the name of Allah made by: Ahmed_Solyman */ #include <bits/stdc++.h> #include <ext/rope> using namespace std; using namespace __gnu_cxx; #pragma GCC optimize("-Ofast") #pragma GCC optimize("-O1") //-------------------------------------------------------------// typedef long long ll; typedef unsigned long long ull; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define PI acos(-1) #define lb lower_bound #define ub upper_bound #define all(v) v.begin(),v.end() #define allr(v) v.rbegin(),v.rend() #define sum_to(n) (n*(n+1))/2 #define pb push_back #define pf push_front #define fil(arr,x) memset(arr,x,sizeof(arr)) #define REP(i,a,b) for (int i=a;i<=b;i++) #define F first #define S second #define MP make_pair const ll mod=1e9+7; int dx[8]={0,1,0,-1,1,1,-1,-1}; int dy[8]={1,0,-1,0,1,-1,-1,1}; //-------------------------------------------------------------// ll lcm(ll a,ll b) { return (max(a,b)/__gcd(a,b))*min(a,b); } void person_bool(bool x) { cout<<(x?"YES":"NO")<<endl; } struct Node { int sum, lazy, tl, tr, l, r; Node() : sum(0), lazy(0), l(-1), r(-1) {} }; const int MAXN = 123456; Node segtree[64 * MAXN]; int cnt = 2; void push_lazy(int node) { if (segtree[node].lazy) { segtree[node].sum = segtree[node].tr - segtree[node].tl + 1; int mid = (segtree[node].tl + segtree[node].tr) / 2; if (segtree[node].l == -1) { segtree[node].l = cnt++; segtree[segtree[node].l].tl = segtree[node].tl; segtree[segtree[node].l].tr = mid; } if (segtree[node].r == -1) { segtree[node].r = cnt++; segtree[segtree[node].r].tl = mid + 1; segtree[segtree[node].r].tr = segtree[node].tr; } segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1; segtree[node].lazy = 0; } } void update(int node, int l, int r) { push_lazy(node); if (l == segtree[node].tl && r == segtree[node].tr) { segtree[node].lazy = 1; push_lazy(node); } else { int mid = (segtree[node].tl + segtree[node].tr) / 2; if (segtree[node].l == -1) { segtree[node].l = cnt++; segtree[segtree[node].l].tl = segtree[node].tl; segtree[segtree[node].l].tr = mid; } if (segtree[node].r == -1) { segtree[node].r = cnt++; segtree[segtree[node].r].tl = mid + 1; segtree[segtree[node].r].tr = segtree[node].tr; } if (l > mid) update(segtree[node].r, l, r); else if (r <= mid) update(segtree[node].l, l, r); else { update(segtree[node].l, l, mid); update(segtree[node].r, mid + 1, r); } push_lazy(segtree[node].l); push_lazy(segtree[node].r); segtree[node].sum = segtree[segtree[node].l].sum + segtree[segtree[node].r].sum; } } int query(int node, int l, int r) { push_lazy(node); if (l == segtree[node].tl && r == segtree[node].tr) return segtree[node].sum; else { int mid = (segtree[node].tl + segtree[node].tr) / 2; if (segtree[node].l == -1) { segtree[node].l = cnt++; segtree[segtree[node].l].tl = segtree[node].tl; segtree[segtree[node].l].tr = mid; } if (segtree[node].r == -1) { segtree[node].r = cnt++; segtree[segtree[node].r].tl = mid + 1; segtree[segtree[node].r].tr = segtree[node].tr; } if (l > mid) return query(segtree[node].r, l, r); else if (r <= mid) return query(segtree[node].l, l, r); else return query(segtree[node].l, l, mid) + query(segtree[node].r, mid + 1, r); } } int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); segtree[1].l=1; segtree[1].r=1e9; int q;cin>>q; int c=0; while(q--){ int t,l,r;cin>>t>>l>>r; if(t==1){ c=query(1,l+c,r+c); cout<<c<<endl; } else{ update(1,l+c,r+c); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...