oj.uz

Submission #27064

# Submission time Handle Problem Language Result Execution time Memory
27064 2017-07-09T06:46:48 Z 시제연(#1120) Editor (BOI15_edi) C++
100 / 100
 1059 ms 399308 KB 
#include <bits/stdc++.h>

using namespace std;

int n;

struct node {
    node *l, *r;
    int val;
    node() {val = 0; l = r = NULL;}
    node(int v):val(v){l = r = NULL;}
    void init(int s = 0, int e = n) {
        if (s==e) return;
        int m = (s+e)>>1;
        if (!l) l = new node();
        if (!r) r = new node();
        l->init(s,m); r->init(m+1,e);
        val = max(l->val,r->val);
    }
    int getv(int S, int E, int s = 0, int e = n) {
        if (e<S||E<s) return 0;
        if (S<=s&&e<=E) return val;
        int m = (s+e)>>1;
        return max(l->getv(S,E,s,m),r->getv(S,E,m+1,e));
    }
    node* upd(int idx, int val, node *ori, int s = 0, int e = n) {
        if (e<idx||idx<s) return ori;
        if (s==e) return new node(val);
        int m = (s+e)>>1;
        if (!l) l = new node();
        l = l->upd(idx,val,ori->l,s,m);
        if (!r) r = new node();
        r = r->upd(idx,val,ori->r,m+1,e);
        this->val = max(l->val,r->val);
        return this;
    }
} *head[300100];

int arr[300100];
int main() {
    int i;

    scanf("%d",&n);
    head[0] = new node();
    head[0]->init();
    for (i=1;i<=n;i++) {
        head[i] = new node();
        scanf("%d",&arr[i]);
        if (arr[i]>0) {
            head[i] = head[i]->upd(0,i,head[0]);
        }
        else {
            arr[i] *= -1;
            head[i] = head[i]->upd(arr[i],i,head[head[i-1]->getv(0,arr[i]-1)-1]);
        }
        printf("%d\n",arr[head[i]->getv(0,0)]);
    }

    return 0;
}

Compilation message

edi.cpp: In function 'int main()':
edi.cpp:43:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
edi.cpp:48:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[i]);
                            ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5552 KB Output is correct
2 Correct 9 ms 10172 KB Output is correct
3 Correct 0 ms 5552 KB Output is correct
4 Correct 0 ms 5552 KB Output is correct
5 Correct 9 ms 10040 KB Output is correct
6 Correct 0 ms 5552 KB Output is correct
7 Correct 6 ms 10304 KB Output is correct
8 Correct 0 ms 5552 KB Output is correct
9 Correct 9 ms 10172 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 399308 KB Output is correct
2 Correct 643 ms 399308 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 189560 KB Output is correct
2 Correct 496 ms 227972 KB Output is correct
3 Correct 549 ms 304136 KB Output is correct
4 Correct 636 ms 399308 KB Output is correct
5 Correct 896 ms 392312 KB Output is correct
6 Correct 659 ms 399308 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5552 KB Output is correct
2 Correct 9 ms 10172 KB Output is correct
3 Correct 0 ms 5552 KB Output is correct
4 Correct 0 ms 5552 KB Output is correct
5 Correct 9 ms 10040 KB Output is correct
6 Correct 0 ms 5552 KB Output is correct
7 Correct 6 ms 10304 KB Output is correct
8 Correct 0 ms 5552 KB Output is correct
9 Correct 9 ms 10172 KB Output is correct
10 Correct 646 ms 399308 KB Output is correct
11 Correct 643 ms 399308 KB Output is correct
12 Correct 416 ms 189560 KB Output is correct
13 Correct 496 ms 227972 KB Output is correct
14 Correct 549 ms 304136 KB Output is correct
15 Correct 636 ms 399308 KB Output is correct
16 Correct 896 ms 392312 KB Output is correct
17 Correct 659 ms 399308 KB Output is correct
18 Correct 846 ms 392312 KB Output is correct
19 Correct 753 ms 392312 KB Output is correct
20 Correct 823 ms 385316 KB Output is correct
21 Correct 566 ms 399308 KB Output is correct
22 Correct 1059 ms 392312 KB Output is correct