Submission #297207

#	Time	Username	Problem	Language	Result	Execution time	Memory
297207		PeppaPig	Editor (BOI15_edi)	C++14	100 / 100	458 ms	207612 KiB

edi

#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 (stderr)

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 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37