oj.uz

Submission #931208

# Submission time Handle Problem Language Result Execution time Memory
931208 2024-02-21T11:26:55 Z VMaksimoski008 Wall (IOI14_wall) C++14
100 / 100
 822 ms 115540 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;
using pii = pair<int, int>;

struct SegTree {
    int n;
    vector<int> tree;
    vector<pii> lazy;

    SegTree(int _n) {
        n = _n;
        tree.resize(4*n+5, 0);
        lazy.resize(4*n+5, {1e9, -1});
    }

    void push(int u, int tl, int tr) {
        if(tl == tr) return ;

        if(lazy[u].first != 1e9) {
            tree[2*u] = min(tree[2*u], lazy[u].first);
            lazy[2*u].first = min(lazy[2*u].first, lazy[u].first);
            lazy[2*u].second = min(lazy[2*u].second, lazy[u].first);

            tree[2*u+1] = min(tree[2*u+1], lazy[u].first);
            lazy[2*u+1].first = min(lazy[2*u+1].first, lazy[u].first);
            lazy[2*u+1].second = min(lazy[2*u+1].second, lazy[u].first);
        }

        if(lazy[u].second != -1) {
            tree[2*u] = max(tree[2*u], lazy[u].second);
            lazy[2*u].first = max(lazy[2*u].first, lazy[u].second);
            lazy[2*u].second = max(lazy[2*u].second, lazy[u].second);

            tree[2*u+1] = max(tree[2*u+1], lazy[u].second);
            lazy[2*u+1].first = max(lazy[2*u+1].first, lazy[u].second);
            lazy[2*u+1].second = max(lazy[2*u+1].second, lazy[u].second);
        }

        lazy[u] = {1e9, -1};
    }

    void update(int u, int tl, int tr, int l, int r, int t, int v) {
        push(u, tl, tr);
        if(tl > tr || l > tr || tl > r) return ;

        if(l <= tl && tr <= r) {
            if(t == 1) {
                tree[u] = max(tree[u], v);
                lazy[u].first = max(lazy[u].first, v);
                lazy[u].second = max(lazy[u].second, v);
            } else {
                tree[u] = min(tree[u], v);
                lazy[u].first = min(lazy[u].first, v);
                lazy[u].second = min(lazy[u].second, v);
            }

            push(u, tl, tr);
            return ;
        }

        int tm = (tl + tr) / 2;
        update(2*u, tl, tm, l, r, t, v);
        update(2*u+1, tm+1, tr, l, r, t, v);
    }

    int query(int u, int tl, int tr, int p) {
        if(tl == tr) return tree[u];
        push(u, tl, tr);
        int tm = (tl + tr) / 2;
        if(p <= tm) return query(2*u, tl, tm, p);
        return query(2*u+1, tm+1, tr, p);
    }   

    void update(int l, int r, int t, int v) { update(1, 0, n-1, l, r, t, v); }
    int query(int p) { return query(1, 0, n-1, p); }
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    SegTree tree(n);
    for(int i=0; i<k; i++) tree.update(left[i], right[i], op[i], height[i]);
    for(int i=0; i<n; i++) finalHeight[i] = tree.query(i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 7 ms 1112 KB Output is correct
5 Correct 5 ms 1112 KB Output is correct
6 Correct 7 ms 1116 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 112 ms 11188 KB Output is correct
3 Correct 165 ms 5972 KB Output is correct
4 Correct 510 ms 18348 KB Output is correct
5 Correct 239 ms 18516 KB Output is correct
6 Correct 260 ms 17832 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 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 900 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 125 ms 11328 KB Output is correct
9 Correct 192 ms 6644 KB Output is correct
10 Correct 584 ms 18348 KB Output is correct
11 Correct 243 ms 18600 KB Output is correct
12 Correct 238 ms 17832 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 113 ms 11088 KB Output is correct
15 Correct 33 ms 2156 KB Output is correct
16 Correct 600 ms 18344 KB Output is correct
17 Correct 238 ms 18092 KB Output is correct
18 Correct 265 ms 18084 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 488 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 7 ms 892 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 112 ms 11172 KB Output is correct
9 Correct 188 ms 6480 KB Output is correct
10 Correct 494 ms 18348 KB Output is correct
11 Correct 247 ms 18704 KB Output is correct
12 Correct 234 ms 17736 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 113 ms 11092 KB Output is correct
15 Correct 34 ms 2136 KB Output is correct
16 Correct 591 ms 18304 KB Output is correct
17 Correct 247 ms 18196 KB Output is correct
18 Correct 242 ms 18088 KB Output is correct
19 Correct 776 ms 115384 KB Output is correct
20 Correct 750 ms 115220 KB Output is correct
21 Correct 747 ms 115276 KB Output is correct
22 Correct 744 ms 115284 KB Output is correct
23 Correct 744 ms 115536 KB Output is correct
24 Correct 736 ms 115308 KB Output is correct
25 Correct 778 ms 115280 KB Output is correct
26 Correct 746 ms 115540 KB Output is correct
27 Correct 822 ms 115284 KB Output is correct
28 Correct 737 ms 115256 KB Output is correct
29 Correct 749 ms 115516 KB Output is correct
30 Correct 746 ms 115348 KB Output is correct