# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
299858 | mohamedsobhi777 | Weighting stones (IZhO11_stones) | C++14 | 87 ms | 4600 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |