oj.uz

Submission #1076671

# Submission time Handle Problem Language Result Execution time Memory
1076671 2024-08-26T15:27:59 Z juicy Wall (IOI14_wall) C++17
100 / 100
 1226 ms 69840 KB 
#include "wall.h"

#include <bits/stdc++.h>

namespace {
    const int N = 2e6 + 5, inf = 1e9;

    int n;
    std::array<int, 2> s[4 * N];

    void bld(int id = 1, int l = 0, int r = n - 1) {
        if (l == r) {
            s[id] = {0, 0}; 
            return;
        }
        s[id] = {-inf, inf};
        int md = (l + r) / 2;
        bld(id * 2, l, md);
        bld(id * 2 + 1, md + 1, r);
    }

    void app(int id, int x, int op) {
        for (auto it : {0, 1}) {
            if (op == 2) {
                s[id][it] = std::min(s[id][it], x);
            } else {
                s[id][it] = std::max(s[id][it], x);
            }
        }
    }

    void psh(int id) {
        if (s[id] != std::array<int, 2>{inf, -inf}) {
            for (auto i : {id * 2, id * 2 + 1}) {
                app(i, s[id][0], 1);
                app(i, s[id][1], 2);
            }
            s[id] = {-inf, inf};
        }
    }

    void upd(int u, int v, int x, int op, int id = 1, int l = 0, int r = n - 1) {
        if (u <= l && r <= v) {
            app(id, x, op);
            return;
        }
        psh(id);
        int md = (l + r) / 2;
        if (u <= md) {
            upd(u, v, x, op, id * 2, l, md);
        } 
        if (md < v) {
            upd(u, v, x, op, id * 2 + 1, md + 1, r);
        }
    }

    int qry(int i, int id = 1, int l = 0, int r = n - 1) {
        if (l == r) {
            assert(s[id][0] == s[id][1]);
            return s[id][0];
        }
        psh(id);
        int md = (l + r) / 2;
        return i <= md ? qry(i, id * 2, l, md) : qry(i, id * 2 + 1, md + 1, r);
    }
}

void buildWall(int n, int k, int *op, int *le, int *ri, int *a, int *res) {
    ::n = n;
    bld();
    for (int i = 0; i < k; ++i) {
        upd(le[i], ri[i], a[i], op[i]);
    }
    for (int i = 0; i < n; ++i) {
        res[i] = qry(i);
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 134 ms 13884 KB Output is correct
3 Correct 150 ms 8044 KB Output is correct
4 Correct 453 ms 20460 KB Output is correct
5 Correct 304 ms 21584 KB Output is correct
6 Correct 314 ms 20144 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 94 ms 13904 KB Output is correct
9 Correct 151 ms 8020 KB Output is correct
10 Correct 541 ms 20468 KB Output is correct
11 Correct 315 ms 21384 KB Output is correct
12 Correct 315 ms 19924 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 126 ms 14072 KB Output is correct
15 Correct 26 ms 2140 KB Output is correct
16 Correct 422 ms 20564 KB Output is correct
17 Correct 277 ms 20020 KB Output is correct
18 Correct 267 ms 20208 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 708 KB Output is correct
5 Correct 6 ms 708 KB Output is correct
6 Correct 6 ms 856 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 89 ms 13904 KB Output is correct
9 Correct 144 ms 8020 KB Output is correct
10 Correct 426 ms 20308 KB Output is correct
11 Correct 263 ms 21584 KB Output is correct
12 Correct 255 ms 19964 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 91 ms 13940 KB Output is correct
15 Correct 26 ms 2132 KB Output is correct
16 Correct 421 ms 20612 KB Output is correct
17 Correct 289 ms 20048 KB Output is correct
18 Correct 259 ms 20052 KB Output is correct
19 Correct 1093 ms 69476 KB Output is correct
20 Correct 1125 ms 67132 KB Output is correct
21 Correct 1116 ms 69840 KB Output is correct
22 Correct 1146 ms 67176 KB Output is correct
23 Correct 1127 ms 67136 KB Output is correct
24 Correct 1119 ms 67176 KB Output is correct
25 Correct 1226 ms 66932 KB Output is correct
26 Correct 1137 ms 69624 KB Output is correct
27 Correct 1134 ms 69480 KB Output is correct
28 Correct 1220 ms 66916 KB Output is correct
29 Correct 1176 ms 67016 KB Output is correct
30 Correct 1102 ms 67076 KB Output is correct