Submission #879533

#TimeUsernameProblemLanguageResultExecution timeMemory
879533alexddWeighting stones (IZhO11_stones)C++17
100 / 100
182 ms4604 KiB
#include<bits/stdc++.h> using namespace std; const int INF = 1e9; int n; pair<int,int> aint[270000]; int lazy[270000]; pair<int,int> combine(pair<int,int> x, pair<int,int> y) { return {min(x.first,y.first), max(x.second,y.second)}; } void propagate(int nod) { lazy[nod*2]+=lazy[nod]; lazy[nod*2+1]+=lazy[nod]; aint[nod*2].first+=lazy[nod]; aint[nod*2].second+=lazy[nod]; aint[nod*2+1].first+=lazy[nod]; aint[nod*2+1].second+=lazy[nod]; lazy[nod]=0; } void upd(int nod, int st, int dr, int le, int ri, int newv) { if(le>ri) return; if(le==st && dr==ri) { aint[nod].first += newv; aint[nod].second += newv; lazy[nod] += newv; return; } propagate(nod); int mij=(st+dr)/2; upd(nod*2,st,mij,le,min(mij,ri),newv); upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv); aint[nod] = combine(aint[nod*2], aint[nod*2+1]); } signed main() { cin>>n; int r,s; for(int i=1;i<=n;i++) { cin>>r>>s; if(s==1) { upd(1,1,n,1,r,-1); } else { upd(1,1,n,1,r,1); } if(aint[1].first<0 && aint[1].second>0) { cout<<"?\n"; } else if(aint[1].first<0) cout<<">\n"; else cout<<"<\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...