Submission #299858

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
299858	2020-09-15T21:28:12 Z	mohamedsobhi777	Weighting stones (IZhO11_stones)	C++14	100 / 100	87 ms	4600 KB

stones

#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 ; 
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	7 ms	768 KB	Output is correct
11	Correct	51 ms	2688 KB	Output is correct
12	Correct	86 ms	4216 KB	Output is correct
13	Correct	87 ms	4472 KB	Output is correct
14	Correct	83 ms	4472 KB	Output is correct
15	Correct	84 ms	4500 KB	Output is correct
16	Correct	82 ms	4472 KB	Output is correct
17	Correct	83 ms	4472 KB	Output is correct
18	Correct	83 ms	4476 KB	Output is correct
19	Correct	82 ms	4472 KB	Output is correct
20	Correct	81 ms	4432 KB	Output is correct
21	Correct	81 ms	4472 KB	Output is correct
22	Correct	86 ms	4600 KB	Output is correct
23	Correct	82 ms	4472 KB	Output is correct
24	Correct	82 ms	4472 KB	Output is correct
25	Correct	81 ms	4472 KB	Output is correct