Submission #299858

#TimeUsernameProblemLanguageResultExecution timeMemory
299858mohamedsobhi777Weighting stones (IZhO11_stones)C++14
100 / 100
87 ms4600 KiB
#include<bits/stdc++.h> /* #pragma GCC optimize("-Ofast") //#pragma GCC optimize("trapv") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-funroll-loops")*/ #define I inline void #define S struct #define vi vector<int> #define vii vector<pair<int,int>> #define pii pair<int,int> #define pll pair<ll,ll> using namespace std ; using ll = long long ; using ld = long double ; const int N = 5e5 + 7 , mod = 1e9 + 7 ; const int inf = N ; // How interesting! int n ; S segtree{ int * tree ; int * lazy ; int size ; int h ; I init(int sz){ tree = new int[sz<<1] ; lazy = new int[sz<<1] ; memset(tree , 0 , sizeof (int) * 2 * sz ) ; memset(lazy , 0 , sizeof (int) * 2 * sz ) ; h = 8 * sizeof (int) - __builtin_clz(size = sz) ; } I apply(int pos , int val){ tree[pos] += val ; if(pos < size) lazy[pos] += val ; } I build(int pos){ while(pos > 1) pos >>=1 , tree[pos] = max(tree[pos<<1] , tree[pos<<1|1] ) + lazy[pos] ; } I pushPar(int x){ for(int s = h ; s ; -- s){ int i = x >> s ; if(lazy[i]){ apply(i<<1,lazy[i]) ; apply(i<<1|1,lazy[i]) ; lazy[i] = 0 ; } } } I addRange(int l , int r, int val){ l+=size ; r+= size; int l0 = l , r0 = r; for( ; l < r ; l >>=1 , r >>=1){ if(l&1)apply(l++ , val) ; if(r&1)apply(-- r,val); } build(l0) ; build(r0-1) ; } int query(int l , int r){ l+=size ; r+=size; int ret = -inf ; pushPar(l) ; pushPar(r-1) ; for(;l < r ; l >>= 1, r >>=1 ){ if(l&1)ret=max(ret , tree[l++] ) ; if(r&1)ret=max(ret , tree[--r] ) ; } return ret ; } } s1 , s2 ; int main(){ ios_base::sync_with_stdio(0) ; cin.tie(0) ; //freopen("in.in" , "r" , stdin) ; cin>> n ; s1.init(n + 10) ; s2.init(n + 10) ; ll A = 0 , B = 0 ; set<int> st1 , st2 ; for(int i = 0 ;i < n;i++){ int a , b ; cin >> a >> b ; int ap = a ; a = n + 1 - a; if(b == 1){ s1.addRange(a , n + 1 , -1) ; s2.addRange(a , n + 1 , 1) ; A+= ap ; }else{ s1.addRange(a , n + 1 , 1) ; s2.addRange(a , n + 1 , -1) ; B+= ap ; } if(!B)cout<<">"; else if(!A) cout<<"<" ; else{ int mask = 0 ; if(s1.query(1 , n + 1) > 0){ mask ++ ; } if(s2.query(1, n + 1 ) > 0){ mask += 2 ; } if(mask == 1) cout<<"<" ; else if(mask == 2) cout<<">" ; else cout<<"?" ; } cout<<"\n" ; } return 0 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...