oj.uz

Submission #503313

# Submission time Handle Problem Language Result Execution time Memory
503313 2022-01-07T16:13:38 Z InternetPerson10 Wall (IOI14_wall) C++17
100 / 100
 1018 ms 234976 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

int BIG = 123456789;

vector<int> ans;

struct SegTree {
    int val = 0;
    int lx, rx, mid;
    int lb = 0, rb = BIG; // bounds
    SegTree *ls = nullptr, *rs = nullptr;
    SegTree(int l, int r) {
        lx = l;
        rx = r;
        mid = (lx + rx)/2;
        if(r - l > 1) {
            int mid = (l + r)/2;
            ls = new SegTree(l, mid);
            rs = new SegTree(mid, r);
        }
    }
    void updateRight(int k) { // Min value, pushes everything on the right
        if(k >= rb) return;
        val = min(val, k);
        if(k >= lb) {
            rb = k;
            return;
        }
        lb = rb = k;
    }
    void updateLeft(int k) { // Max value, pushes everything on the left
        if(k <= lb) return;
        val = max(val, k);
        if(k <= rb) {
            lb = k;
            return;
        }
        lb = rb = k;
    }
    void prop() {
        //cout << "Nice one " << lx << ' ' << rx << ' ' << lb << ' ' << rb << ' '<< val <<"\n";
        if(ls == nullptr) return;
        ls->updateLeft(lb); 
        ls->updateRight(rb);
        rs->updateLeft(lb); 
        rs->updateRight(rb);
        lb = 0; rb = BIG;
    }
    void setMin(int l, int r, int k) {
        prop();
        if(l >= rx || lx >= r) return;
        if(l <= lx && rx <= r) {
            updateRight(k);
            return;
        }
        ls->setMin(l, r, k);
        rs->setMin(l, r, k);
    }
    void setMax(int l, int r, int k) {
        prop();
        if(l >= rx || lx >= r) return;
        if(l <= lx && rx <= r) {
            updateLeft(k);
            return;
        }
        ls->setMax(l, r, k);
        rs->setMax(l, r, k);
    }
    void getAll() {
        prop();
        if(rx - lx == 1) {
            ans[lx] = val;
            return;
        }
        ls->getAll();
        rs->getAll();
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    int siz = 1;
    while(siz <= n) siz *= 2;
    SegTree st(0, siz);
    ans.resize(siz);
    for(int i = 0; i < k; i++) {
        //cout << "Doing " << i << '\n';
        if(op[i] == 2) st.setMin(left[i], right[i]+1, height[i]);
        if(op[i] == 1) st.setMax(left[i], right[i]+1, height[i]);
    }
    st.getAll();
    for(int i = 0; i < n; i++) finalHeight[i] = ans[i];
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 2060 KB Output is correct
5 Correct 7 ms 1996 KB Output is correct
6 Correct 6 ms 2104 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 139 ms 9592 KB Output is correct
3 Correct 210 ms 7236 KB Output is correct
4 Correct 680 ms 24096 KB Output is correct
5 Correct 275 ms 27948 KB Output is correct
6 Correct 291 ms 24720 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 2008 KB Output is correct
5 Correct 6 ms 2112 KB Output is correct
6 Correct 6 ms 2068 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 151 ms 9912 KB Output is correct
9 Correct 209 ms 7664 KB Output is correct
10 Correct 732 ms 24192 KB Output is correct
11 Correct 276 ms 25556 KB Output is correct
12 Correct 268 ms 23852 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 132 ms 9480 KB Output is correct
15 Correct 47 ms 4188 KB Output is correct
16 Correct 850 ms 25180 KB Output is correct
17 Correct 293 ms 25460 KB Output is correct
18 Correct 283 ms 22632 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 2072 KB Output is correct
5 Correct 6 ms 2064 KB Output is correct
6 Correct 6 ms 2068 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 130 ms 9392 KB Output is correct
9 Correct 206 ms 8404 KB Output is correct
10 Correct 665 ms 25332 KB Output is correct
11 Correct 284 ms 24092 KB Output is correct
12 Correct 287 ms 24352 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 136 ms 9392 KB Output is correct
15 Correct 44 ms 4084 KB Output is correct
16 Correct 896 ms 24664 KB Output is correct
17 Correct 319 ms 24044 KB Output is correct
18 Correct 319 ms 22824 KB Output is correct
19 Correct 949 ms 234976 KB Output is correct
20 Correct 890 ms 231504 KB Output is correct
21 Correct 903 ms 234196 KB Output is correct
22 Correct 929 ms 230012 KB Output is correct
23 Correct 911 ms 229868 KB Output is correct
24 Correct 901 ms 231976 KB Output is correct
25 Correct 1018 ms 229812 KB Output is correct
26 Correct 902 ms 233340 KB Output is correct
27 Correct 888 ms 232456 KB Output is correct
28 Correct 899 ms 233208 KB Output is correct
29 Correct 893 ms 232544 KB Output is correct
30 Correct 875 ms 233416 KB Output is correct