oj.uz

Submission #1006643

# Submission time Handle Problem Language Result Execution time Memory
1006643 2024-06-24T06:20:59 Z The_Samurai Wall (IOI14_wall) C++17
100 / 100
 643 ms 59332 KB 
#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
const int inf = 2e9;

vector<int> mn, mx;
int sz;

// first mx, then mn

void impact(int x, int op, int v) {
    if (op == 1) {
        mx[x] = max(mx[x], v);
        if (mn[x] < v) {
            if (2 * x + 2 < mn.size()) {
                impact(2 * x + 1, 2, mn[x]);
                impact(2 * x + 2, 2, mn[x]);
            }
            mn[x] = inf;
        }
    } else {
        mn[x] = min(mn[x], v);
        if (mx[x] >= mn[x]) {
            mx[x] = mn[x];
        }
    }
}

void propagate(int x) {
    if (mx[x] != 0) {
        impact(2 * x + 1, 1, mx[x]);
        impact(2 * x + 2, 1, mx[x]);
        mx[x] = 0;
    }
    if (mn[x] != inf) {
        impact(2 * x + 1, 2, mn[x]);
        impact(2 * x + 2, 2, mn[x]);
        mn[x] = inf;
    }
}

void upd(int l, int r, int op, int v, int x, int lx, int rx) {
    if (l >= rx or lx >= r) return;
    if (l <= lx and rx <= r) {
        impact(x, op, v);
        return;
    }
    propagate(x);
    int mid = (lx + rx) >> 1;
    upd(l, r, op, v, 2 * x + 1, lx, mid);
    upd(l, r, op, v, 2 * x + 2, mid, rx);
}

int get(int i, int x, int lx, int rx) {
    // cout << lx << ' ' << rx << ' ' << mx[x] << ' ' << mn[x] << endl;
    if (rx - lx == 1) {
        return min(mx[x], mn[x]);
    }
    propagate(x);
    int mid = (lx + rx) >> 1;
    if (i < mid) return get(i, 2 * x + 1, lx, mid);
    return get(i, 2 * x + 2, mid, rx);
}

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]) {
    sz = 1;
    while (sz < n) sz *= 2;
    mn.assign(2 * sz - 1, inf); mx.assign(2 * sz - 1, 0);
    vector<int> brute_ans(n);
    for (int i = 0; i < q; i++) {
        upd(left[i], right[i] + 1, op[i], height[i], 0, 0, sz);
#ifdef sunnatov
        for (int j = left[i]; j <= right[i]; j++) {
            if (op[i] == 1) brute_ans[j] = max(brute_ans[j], height[i]);
            else brute_ans[j] = min(brute_ans[j], height[i]);
        }
        // for (int j = 0; j < n; j++) {
        //     finalHeight[j] = get(j, 0, 0, sz);
        //     if (finalHeight[j] != brute_ans[j]) {
        //         cout << j << ' ' << brute_ans[j] << ' ' << finalHeight[j] << endl;
        //     }
        //     assert(finalHeight[j] == brute_ans[j]);
        // }
#endif
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = get(i, 0, 0, sz);
#ifdef sunnatov
        if (finalHeight[i] != brute_ans[i]) {
            cout << i << ' ' << brute_ans[i] << ' ' << finalHeight[i] << endl;
        }
        assert(finalHeight[i] == brute_ans[i]);
#endif
    }
}

Compilation message

wall.cpp: In function 'void impact(int, int, int)':
wall.cpp:15:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |             if (2 * x + 2 < mn.size()) {
      |                 ~~~~~~~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.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 348 KB Output is correct
4 Correct 8 ms 864 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 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 79 ms 8020 KB Output is correct
3 Correct 107 ms 4176 KB Output is correct
4 Correct 315 ms 11088 KB Output is correct
5 Correct 165 ms 11212 KB Output is correct
6 Correct 156 ms 11260 KB Output is correct

Subtask #3
29.0 / 29.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 348 KB Output is correct
4 Correct 6 ms 864 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 79 ms 8044 KB Output is correct
9 Correct 115 ms 4200 KB Output is correct
10 Correct 311 ms 11092 KB Output is correct
11 Correct 165 ms 11208 KB Output is correct
12 Correct 152 ms 11372 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 87 ms 8048 KB Output is correct
15 Correct 34 ms 1616 KB Output is correct
16 Correct 636 ms 11084 KB Output is correct
17 Correct 173 ms 11088 KB Output is correct
18 Correct 163 ms 11088 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 1 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 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 98 ms 8068 KB Output is correct
9 Correct 117 ms 4184 KB Output is correct
10 Correct 305 ms 10880 KB Output is correct
11 Correct 164 ms 11212 KB Output is correct
12 Correct 141 ms 11208 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 80 ms 8128 KB Output is correct
15 Correct 33 ms 1620 KB Output is correct
16 Correct 643 ms 11088 KB Output is correct
17 Correct 171 ms 11092 KB Output is correct
18 Correct 167 ms 11040 KB Output is correct
19 Correct 488 ms 59004 KB Output is correct
20 Correct 538 ms 56660 KB Output is correct
21 Correct 514 ms 59332 KB Output is correct
22 Correct 538 ms 56620 KB Output is correct
23 Correct 474 ms 56692 KB Output is correct
24 Correct 551 ms 56660 KB Output is correct
25 Correct 538 ms 56692 KB Output is correct
26 Correct 512 ms 59036 KB Output is correct
27 Correct 547 ms 59188 KB Output is correct
28 Correct 521 ms 56652 KB Output is correct
29 Correct 564 ms 56616 KB Output is correct
30 Correct 563 ms 56620 KB Output is correct