Submission #711683

#	Time	Username	Problem	Language	Result	Execution time	Memory
711683		Darren0724	Weighting stones (IZhO11_stones)	C++17	100 / 100	70 ms	16916 KiB

stones

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
const int mod=1e9+7;
const int INF=2e18;
const int N=100005;
struct seg{
    int l,r,m;
    seg *lc,*rc;
    int val=0,mn=0,mx=0,lz=0;
    int rmax(){
        return mx+lz;
    }
    int rmin(){
        return mn+lz;
    }
    void pull(){
        mn=min(lc->rmin(),rc->rmin());
        mx=max(lc->rmax(),rc->rmax());
    }
    void push(){
        lc->lz+=lz;
        rc->lz+=lz;
        lz=0;
    }
    seg(int l1,int r1){
        l=l1,r=r1;
        m=(l+r)>>1;
        if(r-l==1){
            return;
        }
        lc=new seg(l,m);
        rc=new seg(m,r);
    }
    void add(int a,int b,int x){
        if(a<=l&&b>=r){
            //cout<<l<<' '<<r<<' '<<x<<endl;
            lz+=x;
            return;
        }
        push();
        if(a<m){
            lc->add(a,b,x);
        }
        if(b>m){
            rc->add(a,b,x);
        }
        pull();
    }
};
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    seg* tr=new seg(0,N);
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        tr->add(1,a+1,(b==1?1:-1));
        if(tr->mn==0){
            cout<<">\n";
        }
        else if(tr->mx==0){
            cout<<"<\n";
        }
        else{
            cout<<"?\n";
        }
    }


    return 0;
}

• Subtask 1: 100 / 100