oj.uz

Submission #581419

# Submission time Handle Problem Language Result Execution time Memory
581419 2022-06-22T15:43:37 Z Josia Wall (IOI14_wall) C++14
100 / 100
 1857 ms 48088 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;



struct segtree {
    struct node {
        int Max;
        int Min;

        node() {
            Max = 1e9;
            Min = -1e9;
        }
    };
    vector<node> tree;

    node op(node a, node b) {
        node res;
        res.Min = max(a.Min, b.Min);
        res.Max = min(a.Max, b.Max);
        if (res.Min > res.Max) {
            if (b.Min > a.Max) {
                res.Max = b.Min;
            }
            if (b.Max < a.Min) {
                res.Min = b.Max;
            }
        }
        return res;
    }


    node queryAll() {
        return tree[1];
    }

    void update(int v, int rl, int rr, int pos, node x) {
        if (rl == rr) {
            tree[v] = x; return;
        }
        int rm = (rl + rr) / 2;
        if (pos <= rm) update(v*2, rl, rm, pos, x);
        else update(v*2+1, rm+1, rr, pos, x);

        tree[v] = op(tree[v*2], tree[v*2+1]);
    }
};



struct event {
    int t;
    int index;
    int x;
    bool start; // 1start; 0end
    bool type;  // 1max; 0min
};
bool compare(event a, event b) {
    return vector<int>{a.t, a.index, a.x, a.start, a.type} < vector<int>{b.t, b.index, b.x, b.start, b.type};
}




void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    deque<event> events;
    for (int i=0; i<k; i++) {
        event blub;
        blub.index = i;
        blub.x = height[i];
        blub.type = op[i]-1;
        blub.t = left[i];
        blub.start = 1;
        events.push_back(blub);
        blub.t = right[i]+1;
        blub.start = 0;
        events.push_back(blub);
    }

    sort(events.begin(), events.end(), compare);

    segtree seg;

    seg.tree.assign(k*4, segtree::node());


    for (int i = 0; i<n; i++) {
        while (events[0].t == i) {
            if (events[0].start == 0) {
                seg.update(1, 0, k-1, events[0].index, segtree::node());
            }

            else {
                segtree::node newOp;
                if (events[0].type) {newOp.Max = events[0].x; newOp.Min = -1e9;}
                else {newOp.Min = events[0].x; newOp.Max = 1e9;}
                seg.update(1, 0, k-1, events[0].index, newOp);
            }

            events.pop_front();
        }

        finalHeight[i] = max(0, seg.queryAll().Min);
    }

    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 9 ms 596 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 11 ms 724 KB Output is correct
5 Correct 10 ms 712 KB Output is correct
6 Correct 10 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1353 ms 40188 KB Output is correct
3 Correct 576 ms 17036 KB Output is correct
4 Correct 1546 ms 40552 KB Output is correct
5 Correct 1470 ms 40540 KB Output is correct
6 Correct 1495 ms 40536 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 10 ms 596 KB Output is correct
3 Correct 4 ms 392 KB Output is correct
4 Correct 12 ms 708 KB Output is correct
5 Correct 11 ms 724 KB Output is correct
6 Correct 10 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1260 ms 40144 KB Output is correct
9 Correct 585 ms 16944 KB Output is correct
10 Correct 1542 ms 40564 KB Output is correct
11 Correct 1500 ms 40576 KB Output is correct
12 Correct 1461 ms 40552 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1278 ms 40192 KB Output is correct
15 Correct 79 ms 2892 KB Output is correct
16 Correct 1722 ms 40560 KB Output is correct
17 Correct 1429 ms 40512 KB Output is correct
18 Correct 1488 ms 40536 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 14 ms 676 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 16 ms 704 KB Output is correct
5 Correct 11 ms 704 KB Output is correct
6 Correct 11 ms 708 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1270 ms 40144 KB Output is correct
9 Correct 583 ms 16816 KB Output is correct
10 Correct 1554 ms 40532 KB Output is correct
11 Correct 1426 ms 40540 KB Output is correct
12 Correct 1440 ms 40536 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1314 ms 40188 KB Output is correct
15 Correct 85 ms 2764 KB Output is correct
16 Correct 1570 ms 40552 KB Output is correct
17 Correct 1388 ms 40540 KB Output is correct
18 Correct 1417 ms 40536 KB Output is correct
19 Correct 1462 ms 48020 KB Output is correct
20 Correct 1506 ms 48020 KB Output is correct
21 Correct 1483 ms 47984 KB Output is correct
22 Correct 1460 ms 48000 KB Output is correct
23 Correct 1472 ms 47916 KB Output is correct
24 Correct 1374 ms 47908 KB Output is correct
25 Correct 1583 ms 47964 KB Output is correct
26 Correct 1404 ms 48020 KB Output is correct
27 Correct 1626 ms 47968 KB Output is correct
28 Correct 1857 ms 47964 KB Output is correct
29 Correct 1420 ms 48088 KB Output is correct
30 Correct 1418 ms 47960 KB Output is correct