Submission #481010

#TimeUsernameProblemLanguageResultExecution timeMemory
481010FatihSolakWeighting stones (IZhO11_stones)C++17
100 / 100
261 ms7620 KiB
#include <bits/stdc++.h> using namespace std; struct SegTree{ vector<int> t,lazy; SegTree(int size){ t.assign(4*size+5,1e9); lazy.assign(4*size+5,0); } void push(int v){ t[v*2] += lazy[v]; t[v*2+1] += lazy[v]; lazy[v*2] += lazy[v]; lazy[v*2+1] += lazy[v]; lazy[v] = 0; } void upd(int v,int tl,int tr,int l,int r,int val){ if(r < tl || tr < l)return; if(l <= tl && tr <= r){ t[v] += val; lazy[v] += val; return; } push(v); int tm = (tl + tr)/2; upd(v*2,tl,tm,l,r,val); upd(v*2+1,tm+1,tr,l,r,val); t[v] = min(t[v*2],t[v*2+1]); } int get(int v,int tl,int tr,int l,int r){ if(r < tl || tr < l)return 1e9; if(l <= tl && tr <= r)return t[v]; push(v); int tm = (tl + tr)/2; return min(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r)); } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); #ifdef Local freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int n; cin >> n; SegTree t1(n); SegTree t2(n); for(int i=1;i<=n;i++){ int r,s; cin >> r >> s; if(s == 1){ t1.upd(1,1,n,1,r-1,-1); t1.upd(1,1,n,r,r,-(int)1e9); t2.upd(1,1,n,1,r,1); } if(s == 2){ t2.upd(1,1,n,1,r-1,-1); t2.upd(1,1,n,r,r,-(int)1e9); t1.upd(1,1,n,1,r,1); } if(t1.get(1,1,n,1,n) > 0){ cout << '<'; } else if(t2.get(1,1,n,1,n) > 0){ cout << '>'; } else cout << '?'; cout << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...