oj.uz

Submission #856006

# Submission time Handle Problem Language Result Execution time Memory
856006 2023-10-02T14:16:46 Z ntkphong Wall (IOI14_wall) C++14
100 / 100
 785 ms 99432 KB 
#include "wall.h"
#include "bits/stdc++.h"
using namespace std;

const int inf = 1e9 + 1;

struct Node {
    int L, R;

    friend Node operator + (Node a, Node b) {
        Node c;

        c.L = max(a.L, b.L);
        c.R = min(a.R, b.R);

        if(c.L > c.R) {
            if(c.L == a.L) c.L = c.R;
            if(c.R == a.R) c.R = c.L;
        }

        return c;
    }
};

vector<Node> ST;

void down(int id) {
    Node x = ST[id];
    ST[id * 2] = ST[id * 2] + x;
    ST[id * 2 + 1] = ST[id * 2 + 1] + x;
    ST[id] = {0, inf};
}

void update(int id, int l, int r, int u, int v, Node x) {
    if(r < u || v < l) return ;

    if(u <= l && r <= v) {
        ST[id] = ST[id] + x;
        return ;
    }

    down(id);
    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, v, x);
    update(id * 2 + 1, mid + 1, r, u, v, x);
}

Node get(int id, int l, int r, int x) {
    if(l == r) return ST[id];

    down(id);
    int mid = (l + r) / 2;
    if(x <= mid) {
        return get(id * 2, l, mid, x);
    } else {
        return get(id * 2 + 1, mid + 1, r, x);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    ST.resize(4 * n + 4);
    for(int i = 1; i <= 4 * n; i ++) ST[i] = {0, inf};

    for(int i = 0; i < k; i ++) {
        Node x = {0, inf};

        if(op[i] == 1) x.L = height[i];
        if(op[i] == 2) x.R = height[i];

        update(1, 1, n, left[i] + 1, right[i] + 1, x);
    }

    for(int i = 0; i < n; i ++) {
        finalHeight[i] = get(1, 1, n, i + 1).L;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 892 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 964 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 99 ms 13908 KB Output is correct
3 Correct 122 ms 8092 KB Output is correct
4 Correct 310 ms 21584 KB Output is correct
5 Correct 199 ms 22624 KB Output is correct
6 Correct 196 ms 21068 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 4 ms 960 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 100 ms 14008 KB Output is correct
9 Correct 118 ms 7924 KB Output is correct
10 Correct 312 ms 21584 KB Output is correct
11 Correct 204 ms 22388 KB Output is correct
12 Correct 196 ms 20896 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 105 ms 13852 KB Output is correct
15 Correct 25 ms 2140 KB Output is correct
16 Correct 422 ms 21768 KB Output is correct
17 Correct 205 ms 21196 KB Output is correct
18 Correct 204 ms 21328 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 5 ms 856 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 964 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 102 ms 13920 KB Output is correct
9 Correct 120 ms 8272 KB Output is correct
10 Correct 313 ms 21580 KB Output is correct
11 Correct 203 ms 22612 KB Output is correct
12 Correct 198 ms 21108 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 103 ms 14032 KB Output is correct
15 Correct 24 ms 2128 KB Output is correct
16 Correct 414 ms 21820 KB Output is correct
17 Correct 202 ms 21196 KB Output is correct
18 Correct 225 ms 21076 KB Output is correct
19 Correct 698 ms 99408 KB Output is correct
20 Correct 785 ms 96452 KB Output is correct
21 Correct 704 ms 99324 KB Output is correct
22 Correct 709 ms 96688 KB Output is correct
23 Correct 649 ms 96776 KB Output is correct
24 Correct 693 ms 96708 KB Output is correct
25 Correct 669 ms 96852 KB Output is correct
26 Correct 677 ms 99432 KB Output is correct
27 Correct 714 ms 99300 KB Output is correct
28 Correct 655 ms 96752 KB Output is correct
29 Correct 662 ms 96840 KB Output is correct
30 Correct 670 ms 96776 KB Output is correct