Submission #48428

#TimeUsernameProblemLanguageResultExecution timeMemory
48428ernestvwWeighting stones (IZhO11_stones)C++11
100 / 100
206 ms13996 KiB
#include <bits/stdc++.h> using namespace std; typedef vector<int> vi; const int maxn = 1<<17; class SegmentTree { public: int n; vi sum,minsuffix,maxsuffix; SegmentTree(int _n) : n(_n), sum(2*_n,0), minsuffix(2*_n,0), maxsuffix(2*_n,0) {} void update(int i,int v) { i+=n; maxsuffix[i]=minsuffix[i]=sum[i]=v; while((i/=2)>0) { sum[i]=sum[2*i]+sum[2*i+1]; minsuffix[i]=min(minsuffix[2*i]+sum[2*i+1],minsuffix[2*i+1]); maxsuffix[i]=max(maxsuffix[2*i]+sum[2*i+1],maxsuffix[2*i+1]); } } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin>>N; SegmentTree segTree(maxn); for(int i=1;i<=N;i++) { int w; int s; cin>>w>>s; segTree.update(w-1, s==1 ? 1 : -1); bool rHeavier = segTree.minsuffix[1]<0; bool lHeavier = segTree.maxsuffix[1]>0; if(rHeavier && lHeavier) cout<<'?'<<endl; else if(rHeavier) cout<<'<'<<endl; else if(lHeavier) cout<<'>'<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...