oj.uz

답안 #299858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299858 2020-09-15T21:28:12 Z mohamedsobhi777 돌 무게 재기 (IZhO11_stones) C++14
100 / 100
 87 ms 4600 KB 
#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

# 결과 실행 시간 메모리 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