oj.uz

Submission #823978

# Submission time Handle Problem Language Result Execution time Memory
823978 2023-08-13T10:55:26 Z annabeth9680 Wall (IOI14_wall) C++17
100 / 100
 448 ms 69544 KB 
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
#define FF first
#define SS second
const int inf = 2000000011;
const pair<int,int> def = MP(-inf, inf);
int N, Q;
pair<int,int> T[8000000];
void init(int t = 1, int tl = 0, int tr = N - 1) {
    if (tl == 0 && tr == N - 1)
        T[t] = MP(0, 0);
    else 
        T[t] = def;
    if (tl == tr) return;
    int tm = (tl + tr) >> 1;
    init(t << 1, tl, tm);
    init(t << 1 | 1, tm + 1, tr);
}
pair<int,int> push(pair<int,int> a, pair<int,int> b) {
    if (a.SS < b.FF) 
        return MP(a.SS, a.SS);
    if (b.SS < a.FF)
        return MP(a.FF, a.FF);
    return MP(max(a.FF, b.FF), min(a.SS, b.SS));
}
void pushdown(int t) {
    if (T[t] != def) {
        T[t << 1] = push(T[t], T[t << 1]);
        T[t << 1 | 1] = push(T[t], T[t << 1 | 1]);
        T[t] = def;
    }
}
void update(int l, int r, pair<int,int> v, int t = 1, int tl = 0, int tr = N - 1) {
    if (r < tl || tr < l)
        return;
    if (l <= tl && tr <= r) {
        T[t] = push(v, T[t]);
        return;
    }
    if (tl != tr)
        pushdown(t);
    int tm = (tl + tr) >> 1;
    update(l, r, v, t << 1, tl, tm);
    update(l, r, v, t << 1 | 1, tm + 1, tr);
}
void pushall(int* ans, int t = 1, int tl = 0, int tr = N - 1) {
    if (tl == tr) {
        ans[tl] = T[t].FF;
        return;
    }
    else 
        pushdown(t);
    int tm = (tl + tr) >> 1;
    pushall(ans, t << 1, tl, tm);
    pushall(ans, t << 1 | 1, tm + 1, tr);
}
void buildWall(int n, int k, int* op, int* lb, int* rb, int* h, int* ans) {
    N = n, Q = k;
    init();
    for (int q = 0; q < Q; q++) {
        pair<int,int> v = def;
        if (op[q] == 1) v.FF = h[q];
        else if (op[q] == 2) v.SS = h[q];
        update(lb[q], rb[q], v);
    }
    pushall(ans);
}
int n, q, op[500005], lb[500005], rb[500005], h[500005], ans[500005];

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 3 ms 832 KB Output is correct
6 Correct 3 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 111 ms 13944 KB Output is correct
3 Correct 111 ms 7884 KB Output is correct
4 Correct 317 ms 20360 KB Output is correct
5 Correct 188 ms 21460 KB Output is correct
6 Correct 181 ms 19836 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 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 836 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 111 ms 13932 KB Output is correct
9 Correct 114 ms 7884 KB Output is correct
10 Correct 313 ms 20404 KB Output is correct
11 Correct 189 ms 21544 KB Output is correct
12 Correct 181 ms 19872 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 118 ms 13880 KB Output is correct
15 Correct 23 ms 2020 KB Output is correct
16 Correct 411 ms 20600 KB Output is correct
17 Correct 194 ms 20004 KB Output is correct
18 Correct 197 ms 20072 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 111 ms 13964 KB Output is correct
9 Correct 111 ms 7884 KB Output is correct
10 Correct 316 ms 20528 KB Output is correct
11 Correct 191 ms 21356 KB Output is correct
12 Correct 181 ms 19788 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 118 ms 13940 KB Output is correct
15 Correct 25 ms 2012 KB Output is correct
16 Correct 412 ms 20572 KB Output is correct
17 Correct 198 ms 20052 KB Output is correct
18 Correct 194 ms 20024 KB Output is correct
19 Correct 448 ms 69544 KB Output is correct
20 Correct 438 ms 67028 KB Output is correct
21 Correct 440 ms 69496 KB Output is correct
22 Correct 444 ms 66968 KB Output is correct
23 Correct 435 ms 67020 KB Output is correct
24 Correct 439 ms 66996 KB Output is correct
25 Correct 440 ms 67104 KB Output is correct
26 Correct 442 ms 69452 KB Output is correct
27 Correct 441 ms 69532 KB Output is correct
28 Correct 440 ms 67000 KB Output is correct
29 Correct 434 ms 67020 KB Output is correct
30 Correct 437 ms 67008 KB Output is correct