oj.uz

Submission #886103

# Submission time Handle Problem Language Result Execution time Memory
886103 2023-12-11T13:10:46 Z fve5 Editor (BOI15_edi) C++17
100 / 100
 506 ms 367880 KB 
#include <bits/stdc++.h>
using namespace std;
 
class SegTree {
    struct Node {
        int level;
        int edit;

        Node *lc, *rc;
 
        Node(int level, int edit, Node *lc, Node *rc) :
            level(level), edit(edit), lc(lc), rc(rc) { }
    };
 
    vector<Node*> roots;
    int size;
    int idx;
    
    Node* build(int nb, int ne) {
        if (nb + 1 == ne) return new Node(INT_MAX, false, NULL, NULL);
        Node *lc = build(nb, (nb + ne) / 2);
        Node *rc = build((nb + ne) / 2, ne);
        return new Node(INT_MAX, false, lc, rc);
    }
 
    int find_op(int level, Node *node, int nb, int ne) {
        if (nb + 1 == ne) return nb;
        if (node->rc->level < level) return find_op(level, node->rc, (nb + ne) / 2, ne);
        return find_op(level, node->lc, nb, (nb + ne) / 2);
    }
 
    Node *copy(int l, int r, Node *source, Node *target, int nb, int ne) {
        if (ne <= l || nb >= r) return target;
        if (l <= nb && ne <= r) return source;
 
        Node *lc = copy(l, r, source->lc, target->lc, nb, (nb + ne) / 2);
        Node *rc = copy(l, r, source->rc, target->rc, (nb + ne) / 2, ne);
        return new Node(min(lc->level, rc->level), rc->edit ?: lc->edit, lc, rc);
    }
 
    Node *update(int pos, int op, Node *node, int nb, int ne) {
        if (ne <= pos || nb > pos) return node;
        if (nb + 1 == ne)
            return new Node(op < 0 ? -op : 0, op > 0 ? op : 0, NULL, NULL);
        
        Node *lc = node->lc;
        Node *rc = node->rc;
 
        if (pos >= (nb + ne) / 2) rc = update(pos, op, node->rc, (nb + ne) / 2, ne);
        else lc = update(pos, op, node->lc, nb, (nb + ne) / 2);
 
        return new Node(min(lc->level, rc->level), rc->edit ?: lc->edit, lc, rc);
    }
 
public:
 
    int apply(int op) {
        if (op > 0) {
            roots.push_back(update(idx, op, roots.back(), 0, size));
        } else {
            int undone = find_op(-op, roots.back(), 0, size);
            Node *temp = copy(0, undone + 1, roots[undone], roots.back(), 0, size);
            roots.push_back(update(idx, op, temp, 0, size));
        }
 
        idx++;
        return roots.back()->edit;
    }
 
    SegTree(int size) : size(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 4 ms 3676 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 4444 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 5 ms 3644 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 5 ms 3676 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 285624 KB Output is correct
2 Correct 361 ms 287040 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 135692 KB Output is correct
2 Correct 210 ms 165220 KB Output is correct
3 Correct 372 ms 286908 KB Output is correct
4 Correct 370 ms 285764 KB Output is correct
5 Correct 362 ms 286648 KB Output is correct
6 Correct 344 ms 284976 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 4 ms 3676 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 4444 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 5 ms 3644 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 5 ms 3676 KB Output is correct
10 Correct 365 ms 285624 KB Output is correct
11 Correct 361 ms 287040 KB Output is correct
12 Correct 170 ms 135692 KB Output is correct
13 Correct 210 ms 165220 KB Output is correct
14 Correct 372 ms 286908 KB Output is correct
15 Correct 370 ms 285764 KB Output is correct
16 Correct 362 ms 286648 KB Output is correct
17 Correct 344 ms 284976 KB Output is correct
18 Correct 349 ms 285464 KB Output is correct
19 Correct 383 ms 286996 KB Output is correct
20 Correct 506 ms 367880 KB Output is correct
21 Correct 366 ms 287416 KB Output is correct
22 Correct 385 ms 287480 KB Output is correct