Submission #894342

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
894342	2023-12-28T06:56:37 Z	zeta7532	Weighting stones (IZhO11_stones)	C++17	100 / 100	223 ms	7872 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	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