oj.uz

답안 #894342

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
894342 2023-12-28T06:56:37 Z zeta7532 돌 무게 재기 (IZhO11_stones) C++17
100 / 100
 223 ms 7872 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 428 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 19 ms 860 KB Output is correct
11 Correct 132 ms 4272 KB Output is correct
12 Correct 213 ms 6992 KB Output is correct
13 Correct 203 ms 7508 KB Output is correct
14 Correct 199 ms 7608 KB Output is correct
15 Correct 223 ms 7732 KB Output is correct
16 Correct 201 ms 7428 KB Output is correct
17 Correct 216 ms 7632 KB Output is correct
18 Correct 212 ms 7808 KB Output is correct
19 Correct 215 ms 7472 KB Output is correct
20 Correct 208 ms 7872 KB Output is correct
21 Correct 205 ms 7612 KB Output is correct
22 Correct 207 ms 7600 KB Output is correct
23 Correct 213 ms 7600 KB Output is correct
24 Correct 202 ms 7508 KB Output is correct
25 Correct 200 ms 7440 KB Output is correct