Submission #103015

# Submission time Handle Problem Language Result Execution time Memory
103015 2019-03-28T16:14:51 Z pavel Editor (BOI15_edi) C++14
100 / 100
877 ms 228856 KB
#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

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]);
         ~~~~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 51 ms 33144 KB Output is correct
2 Correct 61 ms 36344 KB Output is correct
3 Correct 53 ms 33116 KB Output is correct
4 Correct 53 ms 33192 KB Output is correct
5 Correct 62 ms 36472 KB Output is correct
6 Correct 60 ms 33144 KB Output is correct
7 Correct 79 ms 36344 KB Output is correct
8 Correct 57 ms 33096 KB Output is correct
9 Correct 66 ms 36344 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 552 ms 227920 KB Output is correct
2 Correct 564 ms 228076 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 422 ms 130732 KB Output is correct
2 Correct 424 ms 150176 KB Output is correct
3 Correct 490 ms 188536 KB Output is correct
4 Correct 586 ms 227964 KB Output is correct
5 Correct 819 ms 228856 KB Output is correct
6 Correct 607 ms 226064 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 51 ms 33144 KB Output is correct
2 Correct 61 ms 36344 KB Output is correct
3 Correct 53 ms 33116 KB Output is correct
4 Correct 53 ms 33192 KB Output is correct
5 Correct 62 ms 36472 KB Output is correct
6 Correct 60 ms 33144 KB Output is correct
7 Correct 79 ms 36344 KB Output is correct
8 Correct 57 ms 33096 KB Output is correct
9 Correct 66 ms 36344 KB Output is correct
10 Correct 552 ms 227920 KB Output is correct
11 Correct 564 ms 228076 KB Output is correct
12 Correct 422 ms 130732 KB Output is correct
13 Correct 424 ms 150176 KB Output is correct
14 Correct 490 ms 188536 KB Output is correct
15 Correct 586 ms 227964 KB Output is correct
16 Correct 819 ms 228856 KB Output is correct
17 Correct 607 ms 226064 KB Output is correct
18 Correct 877 ms 228568 KB Output is correct
19 Correct 609 ms 228472 KB Output is correct
20 Correct 630 ms 227236 KB Output is correct
21 Correct 559 ms 228092 KB Output is correct
22 Correct 859 ms 228856 KB Output is correct