Submission #679997

#	Time	Username	Problem	Language	Result	Execution time	Memory
679997		Karuk	Weighting stones (IZhO11_stones)	C++14	100 / 100	277 ms	3732 KiB

stones

#include<bits/stdc++.h>
using namespace std;
int maxi[400001];
int mini[400001];
int lp[400001];
const int k=(1<<17);
void pushlazy(int cur) {
    if(cur>=k) {
        return;
    }
    maxi[cur*2]+=lp[cur];
    maxi[cur*2+1]+=lp[cur];
    mini[cur*2]+=lp[cur];
    mini[cur*2+1]+=lp[cur];
    lp[cur*2]+=lp[cur];
    lp[cur*2+1]+=lp[cur];
    lp[cur]=0;
    return;
}
void upd(int from,int to,int val,int cur=1,int beg=0,int en=k-1) {
    pushlazy(cur);
    if(to<beg || from>en)return;
    if(from<=beg && en<=to) {
        lp[cur]+=val;
        maxi[cur]+=val;
        mini[cur]+=val;
        pushlazy(cur);
        return;
    }
    int mid=(beg+en)/2;
    upd(from,to,val,cur*2,beg,mid);
    upd(from,to,val,cur*2+1,mid+1,en);
    mini[cur]=min(mini[cur*2],mini[cur*2+1]);
    maxi[cur]=max(maxi[cur*2],maxi[cur*2+1]);
    return;
}
int main() {
    int n;cin>>n;
    for(int i=0;i<n;i++) {
        int x,r;cin>>x>>r;
        if(r==1)upd(0,x,1);
        else upd(0,x,-1);
        if(maxi[1]<=0)cout<<"<"<<endl;
        else if(mini[1]>=0)cout<<">"<<endl;
        else cout<<"?"<<endl;
    }
    return 0;
}

• Subtask 1: 100 / 100