Submission #103015

#	Time	Username	Problem	Language	Result	Execution time	Memory
103015		pavel	Editor (BOI15_edi)	C++14	100 / 100	877 ms	228856 KiB

edi

#include <cstdio>
#include <stack>
#include <set>

using namespace std;
typedef pair<int,int> ii;

const int MAXN = 1<<19;

struct node{
    node *l, *r;
    int x, w;
    node(int v, int y=-1){
        x=y;
        w=v;
        if(w>1){
            l = new node(w/2, y);
            r = new node(w/2, y);
        }else{
            l = r = nullptr;
        }
    }
    node(const node& o){
        x=o.x;w=o.w;l=o.l;r=o.r;
    }
    int query(int l1, int r1){
        if(l1>=w || r1>=w || l1<0 || r1<0) return -1;
        if(r1-l1+1==w) return x;
        return max(l->query(l1, min(r1, w/2-1)), r->query(max(0, l1-w/2), r1-w/2));
    }
    node* change(int idx, int y){
        if(w==1){
            return new node(1, y);
        }else{
            node* nn = new node(*this);
            if(idx<w/2) nn->l = l->change(idx, y);
            else nn->r = r->change(idx-w/2, y);
            nn->x=max(nn->l->x, nn->r->x);
            return nn;
        }
    }
};

int n;
int b[MAXN];
node *seg;
node * st[MAXN];

int main(){
    st[0]=new node(MAXN);
    scanf("%d", &n);
    for(int i=0;i<n;++i){
        scanf("%d", &b[i]);
        seg=st[i];
        if(b[i]>0){
            st[i+1]=seg->change(0, i);
        }else{
            int p = seg->query(0, -b[i]-1);
            seg = st[p];
            st[i+1] = seg->change(-b[i], i);
        }
    }
    for(int i=1;i<=n;++i){
        int k = st[i]->query(0, 0);
        if(k==-1) puts("0");
        else printf("%d\n", b[k]);
    }
}

Compilation message (stderr)

edi.cpp: In function 'int main()':
edi.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
edi.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37