oj.uz

Submission #1114636

# Submission time Handle Problem Language Result Execution time Memory
1114636 2024-11-19T09:45:05 Z _callmelucian Wall (IOI14_wall) C++14
100 / 100
 770 ms 89160 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct IT {
    vector<int> lo, hi;
    IT (int sz) : lo(4 * sz), hi(4 * sz) {}

    void applyRange (int k, int fL, int fR) {
        lo[k] = max(lo[k], fL), hi[k] = max(hi[k], fL);
        lo[k] = min(lo[k], fR), hi[k] = min(hi[k], fR);
    }

    void pushDown (int k) {
        applyRange(2 * k, lo[k], hi[k]), applyRange(2 * k + 1, lo[k], hi[k]);
    }

    void update (int a, int b, int fL, int fR, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b)
            return applyRange(k, fL, fR), void();
        pushDown(k);
        int mid = (l + r) >> 1;
        update(a, b, fL, fR, 2 * k, l, mid);
        update(a, b, fL, fR, 2 * k + 1, mid + 1, r);
        lo[k] = min(lo[2 * k], lo[2 * k + 1]), hi[k] = max(hi[2 * k], hi[2 * k + 1]);
    }

    void dfsPrint (int k, int l, int r, int finalHeight[]) {
        if (l == r) {
            assert(lo[k] == hi[k]);
            return finalHeight[l] = lo[k], void();
        }
        pushDown(k);
        int mid = (l + r) >> 1;
        dfsPrint(2 * k, l, mid, finalHeight);
        dfsPrint(2 * k + 1, mid + 1, r, finalHeight);
        lo[k] = min(lo[2 * k], lo[2 * k + 1]), hi[k] = max(hi[2 * k], hi[2 * k + 1]);
    }
};

void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    IT tree(n);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) tree.update(left[i], right[i], height[i], INT_MAX, 1, 0, n - 1);
        if (op[i] == 2) tree.update(left[i], right[i], INT_MIN, height[i], 1, 0, n - 1);
    }
    tree.dfsPrint(1, 0, n - 1, finalHeight);
}

#ifdef LOCAL
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int op[] = {1, 2, 2, 1, 1, 2}, left[] = {1, 4, 3, 0, 2, 6}, right[] = {8, 9, 6, 5, 2, 7};
    int height[] = {4, 1, 5, 3, 5, 0}, finalHeight[10] = {0};
    buildWall(10, 6, op, left, right, height, finalHeight);

    for (int i = 0; i < 10; i++) cout << finalHeight[i] << " ";

    return 0;
}
#endif // LOCAL

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 6 ms 848 KB Output is correct
5 Correct 5 ms 848 KB Output is correct
6 Correct 5 ms 848 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 93 ms 13896 KB Output is correct
3 Correct 144 ms 8016 KB Output is correct
4 Correct 409 ms 21264 KB Output is correct
5 Correct 250 ms 21832 KB Output is correct
6 Correct 272 ms 20296 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 6 ms 1028 KB Output is correct
5 Correct 5 ms 848 KB Output is correct
6 Correct 5 ms 848 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 95 ms 13964 KB Output is correct
9 Correct 156 ms 7864 KB Output is correct
10 Correct 425 ms 21256 KB Output is correct
11 Correct 272 ms 21764 KB Output is correct
12 Correct 265 ms 20304 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 96 ms 13996 KB Output is correct
15 Correct 22 ms 1872 KB Output is correct
16 Correct 391 ms 21264 KB Output is correct
17 Correct 256 ms 20820 KB Output is correct
18 Correct 247 ms 20564 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 5 ms 848 KB Output is correct
5 Correct 5 ms 708 KB Output is correct
6 Correct 5 ms 848 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 86 ms 13836 KB Output is correct
9 Correct 140 ms 8008 KB Output is correct
10 Correct 421 ms 21464 KB Output is correct
11 Correct 267 ms 21832 KB Output is correct
12 Correct 283 ms 18760 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 95 ms 13864 KB Output is correct
15 Correct 24 ms 1872 KB Output is correct
16 Correct 430 ms 17904 KB Output is correct
17 Correct 270 ms 20808 KB Output is correct
18 Correct 289 ms 20808 KB Output is correct
19 Correct 730 ms 88904 KB Output is correct
20 Correct 717 ms 88908 KB Output is correct
21 Correct 764 ms 88916 KB Output is correct
22 Correct 768 ms 88904 KB Output is correct
23 Correct 674 ms 89088 KB Output is correct
24 Correct 770 ms 88900 KB Output is correct
25 Correct 749 ms 88904 KB Output is correct
26 Correct 624 ms 89160 KB Output is correct
27 Correct 686 ms 88904 KB Output is correct
28 Correct 674 ms 89008 KB Output is correct
29 Correct 675 ms 87588 KB Output is correct
30 Correct 734 ms 88904 KB Output is correct