oj.uz

Submission #886097

# Submission time Handle Problem Language Result Execution time Memory
886097 2023-12-11T13:05:04 Z fve5 Editor (BOI15_edi) C++17
63 / 100
 583 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
 
class SegTree {
    struct Node {
        int level;
        int edit;
 
        int nb, ne;
        Node *lc, *rc;
 
        Node(int level, int edit, int nb, int ne, Node *lc, Node *rc) :
            level(level), edit(edit), nb(nb), ne(ne), lc(lc), rc(rc) { }
    };
 
    vector<Node*> roots;
    int idx;
    
    Node* build(int nb, int ne) {
        if (nb + 1 == ne) return new Node(INT_MAX, false, nb, ne, NULL, NULL);
        Node *lc = build(nb, (nb + ne) / 2);
        Node *rc = build((nb + ne) / 2, ne);
        return new Node(INT_MAX, false, nb, ne, lc, rc);
    }
 
    int find_op(int level, Node *node) {
        if (node->nb + 1 == node->ne) return node->nb;
        if (node->rc->level < level) return find_op(level, node->rc);
        return find_op(level, node->lc);
    }
 
    Node *copy(int l, int r, Node *source, Node *target) {
        if (source->ne <= l || source->nb >= r) return target;
        if (l <= source->nb && source->ne <= r) return source;
 
        Node *lc = copy(l, r, source->lc, target->lc);
        Node *rc = copy(l, r, source->rc, target->rc);
        return new Node(min(lc->level, rc->level), rc->edit ?: lc->edit, source->nb, source->ne, lc, rc);
    }
 
    Node *update(int pos, int op, Node *node) {
        if (node->ne <= pos || node->nb > pos) return node;
        if (node->nb + 1 == node->ne)
            return new Node(op < 0 ? -op : 0, op > 0 ? op : 0, node->nb, node->ne, NULL, NULL);
        
        Node *lc = node->lc;
        Node *rc = node->rc;
 
        if (pos >= (node->nb + node->ne) / 2) rc = update(pos, op, node->rc);
        else lc = update(pos, op, node->lc);
 
        return new Node(min(lc->level, rc->level), rc->edit ?: lc->edit, node->nb, node->ne, lc, rc);
    }
 
public:
 
    int apply(int op) {
        if (op > 0) {
            roots.push_back(update(idx, op, roots.back()));
        } else {
            int undone = find_op(-op, roots.back());
            Node *temp = copy(0, undone + 1, roots[undone], roots.back());
            roots.push_back(update(idx, op, temp));
        }
 
        idx++;
        return roots.back()->edit;
    }
 
    SegTree(int size) : idx(0) {
        roots.push_back(build(0, size));
    }
};
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
 
    SegTree segtree(n);
    while (n--) {
        int a; cin >> a;
        cout << segtree.apply(a) << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 5 ms 5468 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 6584 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 6 ms 5468 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 5 ms 5468 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 428572 KB Output is correct
2 Correct 421 ms 427284 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 203196 KB Output is correct
2 Correct 231 ms 247428 KB Output is correct
3 Correct 493 ms 430452 KB Output is correct
4 Correct 424 ms 428696 KB Output is correct
5 Correct 422 ms 428468 KB Output is correct
6 Correct 398 ms 425428 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 5 ms 5468 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 6584 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 6 ms 5468 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 5 ms 5468 KB Output is correct
10 Correct 439 ms 428572 KB Output is correct
11 Correct 421 ms 427284 KB Output is correct
12 Correct 196 ms 203196 KB Output is correct
13 Correct 231 ms 247428 KB Output is correct
14 Correct 493 ms 430452 KB Output is correct
15 Correct 424 ms 428696 KB Output is correct
16 Correct 422 ms 428468 KB Output is correct
17 Correct 398 ms 425428 KB Output is correct
18 Correct 408 ms 427804 KB Output is correct
19 Correct 402 ms 428212 KB Output is correct
20 Runtime error 583 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -