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...