Submission #881953

#TimeUsernameProblemLanguageResultExecution timeMemory
881953noyancanturkWeighting stones (IZhO11_stones)C++17
100 / 100
42 ms5580 KiB
#ifndef Local #pragma GCC optimize("O3,unroll-loops") const int lim=1e5+100; #else const int lim=3e3; #endif #include <bits/stdc++.h> using namespace std; //#define int long long #define pb push_back const int mod=1e9+7; using pii=pair<int,int>; struct segtree{ int n,lazy[4*lim]; pii tree[4*lim]; segtree(int n):n(n){ memset(lazy,0,sizeof(lazy)); fill(tree,tree+4*lim,pii{0,0}); } void push(int node,int l,int r){ if(!lazy[node])return; tree[node].first+=lazy[node]; tree[node].second+=lazy[node]; if(l^r){ int child=node<<1; lazy[child]+=lazy[node]; lazy[child|1]+=lazy[node]; } lazy[node]=0; } int L,R,VAL; pii merge(pii v1,pii v2){ return pii{min(v1.first,v2.first),max(v1.second,v2.second)}; } pii update(int l,int r,int node){ push(node,l,r); if(r<L||R<l){ return tree[node]; } if(L<=l&&r<=R){ lazy[node]+=VAL; push(node,l,r); return tree[node]; } int mid=(l+r)>>1,child=node<<1; return tree[node]=merge(update(l,mid,child),update(mid+1,r,child|1)); } void Update(int l,int r,int val){ L=l,R=r,VAL=val; update(1,n,1); } }; void solve(){ int n; cin>>n; segtree a(n); for(int i=0;i<n;i++){ int v,s; cin>>v>>s; a.Update(1,v,s==1?1:-1); if(a.tree[1].first<0&&0<a.tree[1].second){ cout<<"?\n"; }else if(a.tree[1].first<0){ cout<<"<\n"; }else{ cout<<">\n"; } } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); #ifdef Local freopen(".in","r",stdin); freopen(".out","w",stdout); #else //freopen(".in","r",stdin); //freopen(".out","w",stdout); #endif int t=1; //cin>>t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...