Submission #18444

#	Time	Username	Problem	Language	Result	Execution time	Memory
18444		chan492811	Weighting stones (IZhO11_stones)	C++98	100 / 100	76 ms	79208 KiB

stones

#include <cstdio>
#include <algorithm>
using namespace std;
int n,tn=1;
struct data{
    int low,high,l,r,sum;
};
data tree[4000010];
void make_tree(int a){
    if(a>=tn) return;
    make_tree(a*2); make_tree(a*2+1);
    if(tree[a*2].r==0) return;
    if(tree[a*2+1].r==0){ tree[a]=tree[a*2]; return; }
    tree[a].l=tree[a*2].l; tree[a].r=tree[a*2+1].r;
}
void update(int a,int l,int r,int plus){
    if(tree[a].r<l || tree[a].l>r) return;
    if(tree[a].l>=l && tree[a].r<=r){ tree[a].sum+=plus,tree[a].low+=plus,tree[a].high+=plus; return; }
    update(a*2,l,r,plus); update(a*2+1,l,r,plus);
    if(tree[a*2+1].r==0){ tree[a].low=tree[a*2].low; tree[a].high=tree[a*2].high; }
    else { tree[a].low=min(tree[a*2].low,tree[a*2+1].low); tree[a].high=max(tree[a*2].high,tree[a*2+1].high); }
    tree[a].low+=tree[a].sum; tree[a].high+=tree[a].sum;
}
int main(){
    int i,a,s;
    scanf("%d",&n); while(tn<n) tn*=2;
    for(i=tn;i<tn+n;i++) tree[i].r=i-tn+1,tree[i].l=i-tn+1;
    make_tree(1);
    for(i=0;i<n;i++){
        scanf("%d %d",&a,&s);
        if(s==1) update(1,1,a,1);
        else update(1,1,a,-1);
        if(tree[1].low<0 && tree[1].high>0) printf("?\n");
        else if(tree[1].high>0) printf(">\n");
        else printf("<\n");
    }
    return 0;
}

• Subtask 1: 100 / 100