oj.uz

Submission #297207

# Submission time Handle Problem Language Result Execution time Memory
297207 2020-09-11T11:14:01 Z PeppaPig Editor (BOI15_edi) C++14
100 / 100
 458 ms 207612 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5+5;

struct node {
    int val;
    node *l, *r;
    node(int val, node *l, node *r) : val(val), l(l), r(r) {}
};

node* newleaf(int val) { return new node(val, NULL, NULL); }
node* newpar(node *l, node *r) { return new node(min(l->val, r->val), l, r); }

int n, ans[N];
node* t[N];

node* build(int l = 1, int r = n) {
    if(l == r) return newleaf(N);
    int mid = (l + r) >> 1;
    return newpar(build(l, mid), build(mid+1, r));
}

node* update(int x, int k, node *p, int l = 1, int r = n) {
    if(x < l || r < x) return p;
    if(l == r) return newleaf(k);
    int mid = (l + r) >> 1;
    return newpar(update(x, k, p->l, l, mid), update(x, k, p->r, mid+1, r));
}

int find(int x, node *p, int l = 1, int r = n) {
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(p->r->val < x) return find(x, p->r, mid+1, r);
    else return find(x, p->l, l, mid);
}

int main() {
    scanf("%d", &n);
    t[0] = build();
    for(int i = 1, a; i <= n; i++) {
        scanf("%d", &a);
        if(a > 0) {
            ans[i] = a;
            t[i] = update(i, 0, t[i-1]); 
        } else {
            int pre = find(-a, t[i-1]) - 1;
            ans[i] = ans[pre];
            t[i] = update(i, -a, t[pre]);
        }
        printf("%d\n", ans[i]);
    }

    return 0;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 206984 KB Output is correct
2 Correct 437 ms 206968 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 99148 KB Output is correct
2 Correct 268 ms 120568 KB Output is correct
3 Correct 385 ms 162424 KB Output is correct
4 Correct 440 ms 206932 KB Output is correct
5 Correct 446 ms 207612 KB Output is correct
6 Correct 413 ms 204768 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Correct 438 ms 206984 KB Output is correct
11 Correct 437 ms 206968 KB Output is correct
12 Correct 214 ms 99148 KB Output is correct
13 Correct 268 ms 120568 KB Output is correct
14 Correct 385 ms 162424 KB Output is correct
15 Correct 440 ms 206932 KB Output is correct
16 Correct 446 ms 207612 KB Output is correct
17 Correct 413 ms 204768 KB Output is correct
18 Correct 437 ms 207608 KB Output is correct
19 Correct 433 ms 207608 KB Output is correct
20 Correct 458 ms 206120 KB Output is correct
21 Correct 437 ms 206840 KB Output is correct
22 Correct 446 ms 207608 KB Output is correct