oj.uz

Submission #1108303

# Submission time Handle Problem Language Result Execution time Memory
1108303 2024-11-03T17:41:36 Z Ariadna Wall (IOI14_wall) C++14
100 / 100
 1127 ms 89120 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

struct Segtree {
    int n; 
    vector<int> add, rem;
    Segtree(int n): n(n), add(vector<int>(4*n, 0)), rem(vector<int>(4*n, 1e9)) {}

    void Add(int p, int l, int r, int i, int j, int k) {
        if (i > j) return;
        push(p, l, r);
        if (i == l && j == r) {
            add[p] = max(add[p], k); 
            rem[p] = max(add[p], rem[p]);
        } else {
            int m = (l+r)/2;
            Add(2*p, l, m, i, min(m, j), k);
            Add(2*p+1, m+1, r, max(i, m+1), j, k);
            add[p] = min(add[2*p], add[2*p+1]); 
        }
    }

    void Remove(int p, int l, int r, int i, int j, int k) {
        if (i > j) return;
        push(p, l, r);
        if (i == l && j == r) {
            rem[p] = min(rem[p], k); 
            add[p] = min(add[p], rem[p]);
        } else {
            int m = (l+r)/2;
            Remove(2*p, l, m, i, min(m, j), k);
            Remove(2*p+1, m+1, r, max(i, m+1), j, k);
            rem[p] = max(rem[2*p], rem[2*p+1]); 
        }
    }

    void push(int p, int l, int r) {
        if (l != r) {
            add[2*p] = min(rem[p], max(add[2*p], add[p]));
            add[2*p+1] = min(rem[p], max(add[2*p+1], add[p]));
            rem[2*p] = max(add[p], min(rem[2*p], rem[p]));
            rem[2*p+1] = max(add[p], min(rem[2*p+1], rem[p]));
            add[p] = 0;
            rem[p] = 1e9;
        }
    }

    int get(int p, int l, int r, int i) {
        push(p, l, r);
        if (l == r) return min(rem[p], add[p]);
        int m = (l+r)/2;
        if (i <= m) return get(2*p, l, m, i);
        return get(2*p+1, m+1, r, i);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    Segtree St(n);

    for (int i = 0; i < k; ++i) {
        if (op[i] == 1)
            St.Add(1, 0, n-1, left[i], right[i], height[i]);
        else 
            St.Remove(1, 0, n-1, left[i], right[i], height[i]);
    }

    for (int i = 0; i < n; ++i) finalHeight[i] = St.get(1, 0, n-1, i);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 88 ms 8216 KB Output is correct
3 Correct 136 ms 4168 KB Output is correct
4 Correct 417 ms 11708 KB Output is correct
5 Correct 247 ms 11592 KB Output is correct
6 Correct 231 ms 11588 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 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 6 ms 1172 KB Output is correct
5 Correct 6 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 90 ms 13832 KB Output is correct
9 Correct 136 ms 8028 KB Output is correct
10 Correct 413 ms 21388 KB Output is correct
11 Correct 233 ms 21820 KB Output is correct
12 Correct 237 ms 20308 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 84 ms 13892 KB Output is correct
15 Correct 23 ms 1872 KB Output is correct
16 Correct 395 ms 21260 KB Output is correct
17 Correct 237 ms 20808 KB Output is correct
18 Correct 254 ms 20808 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 336 KB Output is correct
4 Correct 5 ms 960 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 6 ms 848 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 102 ms 13848 KB Output is correct
9 Correct 129 ms 8016 KB Output is correct
10 Correct 402 ms 21328 KB Output is correct
11 Correct 252 ms 21832 KB Output is correct
12 Correct 239 ms 20304 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 92 ms 13932 KB Output is correct
15 Correct 32 ms 1872 KB Output is correct
16 Correct 449 ms 21260 KB Output is correct
17 Correct 262 ms 20808 KB Output is correct
18 Correct 262 ms 20808 KB Output is correct
19 Correct 1084 ms 88984 KB Output is correct
20 Correct 1121 ms 89008 KB Output is correct
21 Correct 1127 ms 89004 KB Output is correct
22 Correct 1073 ms 89004 KB Output is correct
23 Correct 1027 ms 89008 KB Output is correct
24 Correct 1041 ms 88904 KB Output is correct
25 Correct 1067 ms 88908 KB Output is correct
26 Correct 1060 ms 89008 KB Output is correct
27 Correct 1067 ms 88904 KB Output is correct
28 Correct 1101 ms 89120 KB Output is correct
29 Correct 1113 ms 89016 KB Output is correct
30 Correct 1040 ms 88904 KB Output is correct