oj.uz

Submission #1043484

# Submission time Handle Problem Language Result Execution time Memory
1043484 2024-08-04T10:03:07 Z deera Wall (IOI14_wall) C++14
100 / 100
 520 ms 89116 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;
#define cint const int
 
class Tree {
    public :
        cint N;
        vector<pair<int, int>> tree;

        Tree(cint &n) : N(n) {
            tree.resize(4 * n, {0, INT_MAX});
        }
 
        void push(cint &x, cint &l, cint &r) {
            if(l == r) {
                return;
            }

            int _l = x * 2;
            int _r = x * 2 + 1;
 
            laze(_l, 1, tree[x].first);
            laze(_l, 2, tree[x].second);
            laze(_r, 1, tree[x].first);
            laze(_r, 2, tree[x].second);

            tree[x] = {0, INT_MAX};
        }
        
        void laze(cint &x, cint &op, cint &v) {
            if(op == 1) {
                tree[x].first = max(tree[x].first, v);
                tree[x].second = max(tree[x].second, tree[x].first);
            } else {
                tree[x].second = min(tree[x].second, v);
                tree[x].first = min(tree[x].first, tree[x].second);
            }
        }
 
        void update(cint &x, cint &l, cint &r, cint &a, cint &b, cint &op, cint &v) {
            if(r < a || b < l) return;
            if(a <= l && r <= b) {
                laze(x, op, v);
            } else {
                push(x, l, r);
                int m = (l + r) / 2;
                update(x * 2, l, m, a, b, op, v);
                update(x * 2 + 1, m + 1, r, a, b, op, v);
            }
        }
 
        void output(cint &x, cint &l, cint &r, int results[]) {
            if(l == r) {
                results[l] = tree[x].first;
                return;
            }
 
            push(x, l, r);
            int m = (l + r) / 2;
            output(x * 2, l, m, results);
            output(x * 2 + 1, m + 1, r, results);
        }
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    Tree tree(n);
    for(int i = 0; i < k; i++) {
        tree.update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
    }
 
    tree.output(1, 0, n - 1, finalHeight);
}

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 3 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 64 ms 8060 KB Output is correct
3 Correct 118 ms 4248 KB Output is correct
4 Correct 350 ms 11652 KB Output is correct
5 Correct 201 ms 11604 KB Output is correct
6 Correct 207 ms 11588 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 3 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 344 KB Output is correct
8 Correct 67 ms 8020 KB Output is correct
9 Correct 121 ms 4180 KB Output is correct
10 Correct 356 ms 11600 KB Output is correct
11 Correct 201 ms 11600 KB Output is correct
12 Correct 205 ms 11540 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 72 ms 8244 KB Output is correct
15 Correct 21 ms 2052 KB Output is correct
16 Correct 366 ms 21216 KB Output is correct
17 Correct 213 ms 20564 KB Output is correct
18 Correct 212 ms 20564 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 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 66 ms 8028 KB Output is correct
9 Correct 125 ms 4304 KB Output is correct
10 Correct 363 ms 11540 KB Output is correct
11 Correct 201 ms 11688 KB Output is correct
12 Correct 199 ms 11596 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 67 ms 8224 KB Output is correct
15 Correct 25 ms 1884 KB Output is correct
16 Correct 355 ms 21264 KB Output is correct
17 Correct 252 ms 20732 KB Output is correct
18 Correct 208 ms 20660 KB Output is correct
19 Correct 464 ms 88916 KB Output is correct
20 Correct 508 ms 88996 KB Output is correct
21 Correct 477 ms 89116 KB Output is correct
22 Correct 465 ms 88912 KB Output is correct
23 Correct 487 ms 88916 KB Output is correct
24 Correct 520 ms 88916 KB Output is correct
25 Correct 508 ms 89000 KB Output is correct
26 Correct 485 ms 88916 KB Output is correct
27 Correct 495 ms 88916 KB Output is correct
28 Correct 483 ms 88912 KB Output is correct
29 Correct 501 ms 88980 KB Output is correct
30 Correct 469 ms 88912 KB Output is correct