oj.uz

Submission #697826

# Submission time Handle Problem Language Result Execution time Memory
697826 2023-02-11T07:05:53 Z ismayil Wall (IOI14_wall) C++17
100 / 100
 954 ms 81848 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
using namespace std;
const ll INF = 1e18;
struct segtree{
    struct node{
        ll mn, mx;
    };
    vector<node> tree;
    ll size;
    segtree(ll n){
        size = 1;
        while(size < n) size *= 2;
        tree.resize(2 * size - 1, {0, INF});
    }
    void propagate(ll x, ll lx, ll rx){
        tree[2 * x + 1].mn = min(tree[x].mx, max(tree[x].mn, tree[2 * x + 1].mn));
        tree[2 * x + 1].mx = max(tree[x].mn, min(tree[x].mx, tree[2 * x + 1].mx));
 
        tree[2 * x + 2].mn = min(tree[x].mx, max(tree[x].mn, tree[2 * x + 2].mn));
        tree[2 * x + 2].mx = max(tree[x].mn, min(tree[x].mx, tree[2 * x + 2].mx));
 
        tree[x].mn = 0;
        tree[x].mx = INF;
    }
    void update(ll op, ll l, ll r, ll h, ll x, ll lx, ll rx){
        if(r <= lx || rx <= l) return;
        if(l <= lx && rx <= r){
            if(op == 1){
                tree[x].mn = max(tree[x].mn, h);
                tree[x].mx = max(tree[x].mx, h);
            }else{
                tree[x].mn = min(tree[x].mn, h);
                tree[x].mx = min(tree[x].mx, h);
            }
            return;
        }
        propagate(x, lx, rx);
        ll mx = (lx + rx) / 2;
        update(op, l, r, h, 2 * x + 1, lx, mx);
        update(op, l, r, h, 2 * x + 2, mx, rx);
    }
    void update(ll op, ll l, ll r, ll h){
        update(op, l, r, h, 0, 0, size);
    }
    ll query(ll pos, ll x, ll lx, ll rx){
        if(rx - lx == 1){
            return tree[x].mn;
        }
        propagate(x, lx, rx);
        ll mx = (lx + rx) / 2;
        if(pos < mx) return query(pos, 2 * x + 1, lx, mx);
        return query(pos, 2 * x + 2, mx, rx);
    }
    ll query(ll pos){
        return query(pos, 0, 0, size);
    }
};
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++) st.update(op[i], left[i], right[i] + 1, height[i]);
    for (int i = 0; i < n; i++) finalHeight[i] = st.query(i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 9 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 120 ms 8028 KB Output is correct
3 Correct 160 ms 4604 KB Output is correct
4 Correct 482 ms 12720 KB Output is correct
5 Correct 267 ms 12620 KB Output is correct
6 Correct 263 ms 12616 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 117 ms 8084 KB Output is correct
9 Correct 164 ms 4568 KB Output is correct
10 Correct 408 ms 12512 KB Output is correct
11 Correct 296 ms 12604 KB Output is correct
12 Correct 263 ms 12556 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 123 ms 8096 KB Output is correct
15 Correct 35 ms 1816 KB Output is correct
16 Correct 469 ms 12700 KB Output is correct
17 Correct 263 ms 12616 KB Output is correct
18 Correct 273 ms 12620 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 120 ms 8128 KB Output is correct
9 Correct 171 ms 4576 KB Output is correct
10 Correct 417 ms 12588 KB Output is correct
11 Correct 277 ms 12620 KB Output is correct
12 Correct 261 ms 12740 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 155 ms 8060 KB Output is correct
15 Correct 30 ms 1816 KB Output is correct
16 Correct 479 ms 12712 KB Output is correct
17 Correct 269 ms 12620 KB Output is correct
18 Correct 268 ms 12684 KB Output is correct
19 Correct 904 ms 81560 KB Output is correct
20 Correct 948 ms 81848 KB Output is correct
21 Correct 954 ms 81652 KB Output is correct
22 Correct 877 ms 81664 KB Output is correct
23 Correct 953 ms 81528 KB Output is correct
24 Correct 910 ms 81608 KB Output is correct
25 Correct 942 ms 81568 KB Output is correct
26 Correct 907 ms 81616 KB Output is correct
27 Correct 915 ms 81680 KB Output is correct
28 Correct 915 ms 81672 KB Output is correct
29 Correct 944 ms 81696 KB Output is correct
30 Correct 938 ms 81552 KB Output is correct