Submission #679997

#TimeUsernameProblemLanguageResultExecution timeMemory
679997KarukWeighting stones (IZhO11_stones)C++14
100 / 100
277 ms3732 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...