Submission #894342

#	Time	Username	Problem	Language	Result	Execution time	Memory
894342		zeta7532	Weighting stones (IZhO11_stones)	C++17	100 / 100	223 ms	7872 KiB

stones

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = int;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)

template <typename T>
struct RMQmax{
    const T INF=0;
    ll N;
    vector<T> dat,lazy;
    RMQmax(ll N_):N(),dat(N_*4,0),lazy(N_*4,INF){
        ll x=1;
        while(N_>x) x*=2;
        N=x;
    }
    void eval(ll k,ll l,ll r){
        if(lazy[k]==0) return;
        if(k<N-1){
            lazy[k*2+1]+=lazy[k];
            lazy[k*2+2]+=lazy[k];
        }
        dat[k]+=lazy[k];
        lazy[k]=0;
    }
    void update(ll a,ll b,T x,ll k,ll l,ll r){
        eval(k,l,r);
        if(a<=l&&r<=b){
            lazy[k]+=x;
            eval(k,l,r);
        }else if(a<r&&l<b){
            update(a,b,x,k*2+1,l,(l+r)/2);
            update(a,b,x,k*2+2,(l+r)/2,r);
            dat[k]=max(dat[k*2+1],dat[k*2+2]);
        }
    }
    void update(ll a,ll b,T x){update(a,b,x,0,0,N);}
    T query_sub(ll a,ll b,ll k,ll l,ll r){
        eval(k,l,r);
        if(r<=a||b<=l){
            return -1e9;
        }else if(a<=l&&r<=b){
            return dat[k];
        }else{
            T vl=query_sub(a,b,k*2+1,l,(l+r)/2);
            T vr=query_sub(a,b,k*2+2,(l+r)/2,r);
            return max(vl,vr);
        }
    }
    T query(ll a,ll b){return query_sub(a,b,0,0,N);}
};

template <typename T>
struct RMQmin{
    const T INF=0;
    ll N;
    vector<T> dat,lazy;
    RMQmin(ll N_):N(),dat(N_*4,0),lazy(N_*4,INF){
        ll x=1;
        while(N_>x) x*=2;
        N=x;
    }
    void eval(ll k,ll l,ll r){
        if(lazy[k]==0) return;
        if(k<N-1){
            lazy[k*2+1]+=lazy[k];
            lazy[k*2+2]+=lazy[k];
        }
        dat[k]+=lazy[k];
        lazy[k]=0;
    }
    void update(ll a,ll b,T x,ll k,ll l,ll r){
        eval(k,l,r);
        if(a<=l&&r<=b){
            lazy[k]+=x;
            eval(k,l,r);
        }else if(a<r&&l<b){
            update(a,b,x,k*2+1,l,(l+r)/2);
            update(a,b,x,k*2+2,(l+r)/2,r);
            dat[k]=min(dat[k*2+1],dat[k*2+2]);
        }
    }
    void update(ll a,ll b,T x){update(a,b,x,0,0,N);}
    T query_sub(ll a,ll b,ll k,ll l,ll r){
        eval(k,l,r);
        if(r<=a||b<=l){
            return 1e9;
        }else if(a<=l&&r<=b){
            return dat[k];
        }else{
            T vl=query_sub(a,b,k*2+1,l,(l+r)/2);
            T vr=query_sub(a,b,k*2+2,(l+r)/2,r);
            return min(vl,vr);
        }
    }
    T query(ll a,ll b){return query_sub(a,b,0,0,N);}
};

int main() {
    ll N;
    cin >> N;
    RMQmin<ll> segmin(N);
    RMQmax<ll> segmax(N);
    rep(i,N){
        ll R,S;
        cin >> R >> S;
        if(S==1) segmin.update(0,R,1),segmax.update(0,R,1);
        if(S==2) segmin.update(0,R,-1),segmax.update(0,R,-1);
        ll valmin=segmin.query(0,N),valmax=segmax.query(0,N);
        if(0<=valmin) cout << '>' << endl;
        if(valmax<=0) cout << '<' << endl;
        if(valmin<0&&0<valmax) cout << '?' << endl;
    }
    return 0;
}

• Subtask 1: 100 / 100