oj.uz

Submission #117356

# Submission time Handle Problem Language Result Execution time Memory
117356 2019-06-15T15:04:11 Z dolphingarlic Wall (IOI14_wall) C++14
100 / 100
 704 ms 99264 KB 
// Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "wall.h"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector<ii>
#define pb push_back
struct node {
    int lo, hi;
    node() {
        lo = 0;
        hi = 1e5;
    }
};
const int maxn = 2e6 + 5;
node st[4 * maxn];
int n;
void change(int p, int op, int v) {
    if (op == 1)
        st[p].lo = max(st[p].lo, v), st[p].hi = max(st[p].hi, v);
    else
        st[p].lo = min(st[p].lo, v), st[p].hi = min(st[p].hi, v);
}
void update(int i, int j, int op, int v, int p = 1, int L = 0, int R = n - 1) {
    if (i > R || j < L) return;
    if (i <= L && R <= j) {
        change(p, op, v);
        return;
    }
    change(2 * p, 1, st[p].lo);
    change(2 * p + 1, 1, st[p].lo);
    change(2 * p, 2, st[p].hi);
    change(2 * p + 1, 2, st[p].hi);
    st[p].lo = 0, st[p].hi = 1e5;
    int M = (L + R) / 2;
    update(i, j, op, v, 2 * p, L, M);
    update(i, j, op, v, 2 * p + 1, M + 1, R);
}
int *arr;
void prop(int p = 1, int L = 0, int R = n - 1) {
    if (L == R) {
        arr[L] = st[p].lo;
        return;
    }
    change(2 * p, 1, st[p].lo);
    change(2 * p + 1, 1, st[p].lo);
    change(2 * p, 2, st[p].hi);
    change(2 * p + 1, 2, st[p].hi);
    int M = (L + R) / 2;
    prop(2 * p, L, M);
    prop(2 * p + 1, M + 1, R);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[],
               int finalHeight[]) {
    n = N;
    arr = finalHeight;
    for (int i = 0; i < k; i++) update(left[i], right[i], op[i], height[i]);
    prop();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 62968 KB Output is correct
2 Correct 56 ms 63120 KB Output is correct
3 Correct 53 ms 62940 KB Output is correct
4 Correct 58 ms 63224 KB Output is correct
5 Correct 54 ms 63224 KB Output is correct
6 Correct 53 ms 63228 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 62972 KB Output is correct
2 Correct 190 ms 76536 KB Output is correct
3 Correct 218 ms 70104 KB Output is correct
4 Correct 543 ms 81144 KB Output is correct
5 Correct 333 ms 82084 KB Output is correct
6 Correct 341 ms 80632 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 62968 KB Output is correct
2 Correct 51 ms 63048 KB Output is correct
3 Correct 50 ms 62996 KB Output is correct
4 Correct 55 ms 63224 KB Output is correct
5 Correct 53 ms 63216 KB Output is correct
6 Correct 53 ms 63224 KB Output is correct
7 Correct 52 ms 62968 KB Output is correct
8 Correct 206 ms 76668 KB Output is correct
9 Correct 225 ms 70264 KB Output is correct
10 Correct 552 ms 81144 KB Output is correct
11 Correct 333 ms 82080 KB Output is correct
12 Correct 325 ms 80504 KB Output is correct
13 Correct 50 ms 62968 KB Output is correct
14 Correct 193 ms 76696 KB Output is correct
15 Correct 77 ms 64280 KB Output is correct
16 Correct 568 ms 81360 KB Output is correct
17 Correct 350 ms 80760 KB Output is correct
18 Correct 339 ms 80632 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 62976 KB Output is correct
2 Correct 52 ms 63100 KB Output is correct
3 Correct 58 ms 63096 KB Output is correct
4 Correct 57 ms 63224 KB Output is correct
5 Correct 55 ms 63224 KB Output is correct
6 Correct 54 ms 63224 KB Output is correct
7 Correct 61 ms 62968 KB Output is correct
8 Correct 193 ms 76636 KB Output is correct
9 Correct 229 ms 70136 KB Output is correct
10 Correct 575 ms 80988 KB Output is correct
11 Correct 341 ms 82064 KB Output is correct
12 Correct 329 ms 80508 KB Output is correct
13 Correct 51 ms 62960 KB Output is correct
14 Correct 193 ms 76536 KB Output is correct
15 Correct 78 ms 64124 KB Output is correct
16 Correct 578 ms 81400 KB Output is correct
17 Correct 345 ms 80660 KB Output is correct
18 Correct 328 ms 80760 KB Output is correct
19 Correct 692 ms 99264 KB Output is correct
20 Correct 674 ms 96652 KB Output is correct
21 Correct 688 ms 99096 KB Output is correct
22 Correct 658 ms 96760 KB Output is correct
23 Correct 685 ms 96716 KB Output is correct
24 Correct 679 ms 96824 KB Output is correct
25 Correct 660 ms 96796 KB Output is correct
26 Correct 704 ms 99244 KB Output is correct
27 Correct 690 ms 99156 KB Output is correct
28 Correct 678 ms 96676 KB Output is correct
29 Correct 678 ms 96868 KB Output is correct
30 Correct 650 ms 96760 KB Output is correct