oj.uz

Submission #1092876

# Submission time Handle Problem Language Result Execution time Memory
1092876 2024-09-25T09:33:53 Z daviedu Wall (IOI14_wall) C++17
100 / 100
 599 ms 75688 KB 
#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int) (a).size()
#define ll long long
#define ld long double
#define pb push_back

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

#define bound array<int, 2>

const bound neutral = {0, INT_MAX};
const bound no_lazy = {-1, -1};
const int MI = 0, MA = INT_MAX;

class Segtree{
public:
    int n;
    vector<int> t, hi, lo; // lazy is not a bound, but an operation with 2 parameters
    Segtree(int size){
        n = 1;
        while (n < size) n <<= 1;
        t.resize(2*n);
        hi.resize(2*n, MA);
        lo.resize(2*n, MI);
    }
    void apply(int i){
        t[i] = max(t[i], lo[i]);
        t[i] = min(t[i], hi[i]);
        hi[i] = MA;
        lo[i] = MI;
    }

    void comb(int down, int i){
        if (hi[down] <= lo[i]) lo[down] = hi[down] = lo[i];
        if (lo[down] >= hi[i]) lo[down] = hi[down] = hi[i];
        else{
            lo[down] = max(lo[down], lo[i]);
            hi[down] = min(hi[down], hi[i]);
        }
    }

    void prop(int i){
        if (lo[i] == MI && hi[i] == MA) return;
        if (i >= n) apply(i);
        else{
            comb(2*i, i);
            comb(2*i+1, i);
            hi[i] = MA;
            lo[i] = MI;
        }
    }
    void update(int l, int r, int i, int a, int b, int v, int op){
        prop(i);
        if (b < l || r < a) return;
        if (a <= l && r <= b){
            if (op == 1) lo[i] = v;
            else hi[i] = v;
            prop(i);
            return;
        }
        int m = (l+r)/2;
        update(l, m, 2*i, a, b, v, op);
        update(m+1, r, 2*i+1, a, b, v, op);
    }
    void update(int l, int r, int v, int op){
        update(0, n-1, 1, l, r, v, op);
    }

    int query(int l, int r, int i, int pos){
        prop(i);
        assert(lo[i] == MI && hi[i] == MA);
        if (l == r && l == pos) return t[i];
        int m = (l+r)/2;
        if (pos <= m) return query(l, m, 2*i, pos);
        else return query(m+1, r, 2*i+1, pos);
    }
    int query(int pos){
        return query(0, n-1, 1, pos);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    Segtree seg (n);
    for (int i=0; i<k; i++){
        seg.update(left[i], right[i], height[i], op[i]);
    }
    for (int i=0; i<n; i++){
        finalHeight[i] = seg.query(i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 3 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 1 ms 344 KB Output is correct
2 Correct 110 ms 13940 KB Output is correct
3 Correct 139 ms 8532 KB Output is correct
4 Correct 406 ms 21332 KB Output is correct
5 Correct 185 ms 21848 KB Output is correct
6 Correct 179 ms 20316 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 5 ms 892 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 3 ms 868 KB Output is correct
7 Correct 0 ms 356 KB Output is correct
8 Correct 86 ms 14060 KB Output is correct
9 Correct 138 ms 8284 KB Output is correct
10 Correct 393 ms 21184 KB Output is correct
11 Correct 197 ms 21840 KB Output is correct
12 Correct 180 ms 20188 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 84 ms 13840 KB Output is correct
15 Correct 29 ms 2136 KB Output is correct
16 Correct 497 ms 21328 KB Output is correct
17 Correct 179 ms 20564 KB Output is correct
18 Correct 176 ms 20692 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 564 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 960 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 94 ms 13920 KB Output is correct
9 Correct 138 ms 8272 KB Output is correct
10 Correct 400 ms 21328 KB Output is correct
11 Correct 180 ms 21844 KB Output is correct
12 Correct 192 ms 20324 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 88 ms 13884 KB Output is correct
15 Correct 28 ms 2140 KB Output is correct
16 Correct 513 ms 21464 KB Output is correct
17 Correct 180 ms 20564 KB Output is correct
18 Correct 185 ms 20680 KB Output is correct
19 Correct 551 ms 75604 KB Output is correct
20 Correct 568 ms 75600 KB Output is correct
21 Correct 599 ms 75688 KB Output is correct
22 Correct 525 ms 75668 KB Output is correct
23 Correct 580 ms 75588 KB Output is correct
24 Correct 572 ms 75600 KB Output is correct
25 Correct 544 ms 75600 KB Output is correct
26 Correct 562 ms 75600 KB Output is correct
27 Correct 558 ms 75600 KB Output is correct
28 Correct 574 ms 75652 KB Output is correct
29 Correct 528 ms 75600 KB Output is correct
30 Correct 534 ms 75600 KB Output is correct