oj.uz

Submission #381222

# Submission time Handle Problem Language Result Execution time Memory
381222 2021-03-24T19:04:37 Z JerryLiu06 Wall (IOI14_wall) C++11
100 / 100
 1689 ms 130924 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int, pair<int, int>> pii;

#define f first
#define s second

pii tree[8000010]; const int INF = 2e9;

bool ckmin(int& A, int B) { return (B < A) ? A = B, true : false; }
bool ckmax(int& A, int B) { return (B > A) ? A = B, true : false; }

void pushdown(int x, int l, int r) {
    ckmin(tree[x].f, tree[x].s.f); ckmax(tree[x].f, tree[x].s.s);
    
    if (l < r) for (int CHILD = 2 * x; CHILD <= 2 * x + 1; CHILD++) {
        ckmax(tree[CHILD].s.s, tree[x].s.s); ckmax(tree[CHILD].s.f, tree[CHILD].s.s);

        ckmin(tree[CHILD].s.f, tree[x].s.f); ckmin(tree[CHILD].s.s, tree[CHILD].s.f);
    }
    tree[x].s.f = INF; tree[x].s.s = 0;
}
void update(int x, int l, int r, int tl, int tr, int T, int H) { int mid = (l + r) / 2;
    pushdown(x, l, r); if (l > tr || r < tl) return ; if (tl <= l && r <= tr) {

        if (T == 1) { ckmax(tree[x].s.s, H); ckmax(tree[x].s.f, tree[x].s.s); }
        if (T == 2) { ckmin(tree[x].s.f, H); ckmin(tree[x].s.s, tree[x].s.f); } return ; 
    }
    update(2 * x, l, mid, tl, tr, T, H); update(2 * x + 1, mid + 1, r, tl, tr, T, H);
    
    pushdown(2 * x, l, mid); pushdown(2 * x + 1, mid + 1, r); tree[x].f = max(tree[2 * x].f, tree[2 * x + 1].f);
}
void genAns(int x, int l, int r, int finalHeight[]) { int mid = (l + r) / 2;
    pushdown(x, l, r); if (l == r) { finalHeight[l - 1] = tree[x].f; return ; }

    genAns(2 * x, l, mid, finalHeight); genAns(2 * x + 1, mid + 1, r, finalHeight);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int i = 1; i <= 4 * N; i++) { tree[i].s.f = INF; tree[i].s.s = 0; }
    
    for (int i = 0; i < K; i++) update(1, 1, N, left[i] + 1, right[i] + 1, op[i], height[i]);

    genAns(1, 1, N, finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 13 ms 1004 KB Output is correct
5 Correct 10 ms 1004 KB Output is correct
6 Correct 10 ms 1004 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 158 ms 8172 KB Output is correct
3 Correct 421 ms 4588 KB Output is correct
4 Correct 1285 ms 13436 KB Output is correct
5 Correct 698 ms 14060 KB Output is correct
6 Correct 686 ms 14076 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 13 ms 1036 KB Output is correct
5 Correct 10 ms 1004 KB Output is correct
6 Correct 10 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 159 ms 8172 KB Output is correct
9 Correct 423 ms 4588 KB Output is correct
10 Correct 1242 ms 13548 KB Output is correct
11 Correct 713 ms 14060 KB Output is correct
12 Correct 680 ms 14188 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 160 ms 8172 KB Output is correct
15 Correct 74 ms 1900 KB Output is correct
16 Correct 1359 ms 13692 KB Output is correct
17 Correct 688 ms 13696 KB Output is correct
18 Correct 692 ms 13804 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 13 ms 1004 KB Output is correct
5 Correct 10 ms 1004 KB Output is correct
6 Correct 10 ms 1008 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 155 ms 8172 KB Output is correct
9 Correct 425 ms 4588 KB Output is correct
10 Correct 1251 ms 13548 KB Output is correct
11 Correct 689 ms 13932 KB Output is correct
12 Correct 683 ms 14060 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 165 ms 8172 KB Output is correct
15 Correct 74 ms 1900 KB Output is correct
16 Correct 1394 ms 13752 KB Output is correct
17 Correct 693 ms 13932 KB Output is correct
18 Correct 702 ms 13804 KB Output is correct
19 Correct 1666 ms 120200 KB Output is correct
20 Correct 1654 ms 128364 KB Output is correct
21 Correct 1654 ms 130668 KB Output is correct
22 Correct 1657 ms 128108 KB Output is correct
23 Correct 1689 ms 128228 KB Output is correct
24 Correct 1660 ms 128348 KB Output is correct
25 Correct 1665 ms 128492 KB Output is correct
26 Correct 1679 ms 130924 KB Output is correct
27 Correct 1658 ms 130764 KB Output is correct
28 Correct 1679 ms 128236 KB Output is correct
29 Correct 1660 ms 128408 KB Output is correct
30 Correct 1660 ms 128364 KB Output is correct