oj.uz

Submission #235987

# Submission time Handle Problem Language Result Execution time Memory
235987 2020-05-30T15:15:18 Z Bilyana Wall (IOI14_wall) C++17
100 / 100
 924 ms 115192 KB 
#include<bits/stdc++.h>
#define f first
#define s second

using namespace std;

const int MAXA = 1e6;
vector<pair<int, int>> st;
vector<pair<int, int>> lp;

void findNewVal(pair<int, int> &l, pair<int, int> &r) {
    l.f = max(l.f, min(r.f, l.s));
    l.s = min(l.s, max(r.s, l.f));
}

void updateLazy(int curr, bool leaf, int pos) {
    if (leaf) {
        findNewVal(st[pos], lp[curr]);
        return;
    }
    findNewVal(lp[curr*2], lp[curr]);
    findNewVal(lp[curr*2+1], lp[curr]);
    lp[curr] = {0, MAXA};

}

void update(int curr, int l, int r, int b, int e, int val, int type) {
    updateLazy(curr, l==r, l);
    if (l > e || r < b) {
        return;
    }

    if (l >= b && r <= e) {
        if (type == 1) {
            lp[curr].f = min(lp[curr].s, val);
        } else if (type == 2) {
            lp[curr].s = max(lp[curr].f, val);
        }
        return;
    }
    int mid = (l+r)/2;
    update(curr*2, l, mid, b, e, val, type);
    update(curr*2+1, mid+1, r, b, e, val, type);
}

void calcAns(int curr, int l, int r) {
    //cerr<<l<<' '<<r<<" - "<<lp[curr].f<<' '<<lp[curr].s<<endl;
    updateLazy(curr, l==r, l);
    if (l == r) {
        return;
    }

    int mid = (l+r)/2;
    calcAns(curr*2, l, mid);
    calcAns(curr*2+1, mid+1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    st.resize(n, {0, MAXA}), lp.resize(4*n, {0, MAXA});
    for (int i=k-1; i>=0; i--) {
        update(1, 0, n-1, left[i], right[i], height[i], op[i]);
    }
    calcAns(1, 0, n-1);
    for (int i=0; i<n; i++) {
        finalHeight[i] = st[i].f;
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 12 ms 1024 KB Output is correct
5 Correct 10 ms 1024 KB Output is correct
6 Correct 11 ms 1024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 183 ms 8312 KB Output is correct
3 Correct 248 ms 4520 KB Output is correct
4 Correct 660 ms 22248 KB Output is correct
5 Correct 385 ms 23288 KB Output is correct
6 Correct 389 ms 21752 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 288 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 14 ms 1024 KB Output is correct
5 Correct 10 ms 1024 KB Output is correct
6 Correct 11 ms 1024 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 184 ms 13924 KB Output is correct
9 Correct 247 ms 8312 KB Output is correct
10 Correct 647 ms 22348 KB Output is correct
11 Correct 385 ms 23392 KB Output is correct
12 Correct 375 ms 21752 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 181 ms 13944 KB Output is correct
15 Correct 47 ms 2168 KB Output is correct
16 Correct 829 ms 22520 KB Output is correct
17 Correct 384 ms 22008 KB Output is correct
18 Correct 389 ms 22008 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 980 KB Output is correct
5 Correct 11 ms 1152 KB Output is correct
6 Correct 10 ms 1024 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 187 ms 13944 KB Output is correct
9 Correct 248 ms 8216 KB Output is correct
10 Correct 624 ms 22392 KB Output is correct
11 Correct 406 ms 23284 KB Output is correct
12 Correct 391 ms 21752 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 183 ms 13948 KB Output is correct
15 Correct 47 ms 2168 KB Output is correct
16 Correct 776 ms 22520 KB Output is correct
17 Correct 376 ms 22008 KB Output is correct
18 Correct 396 ms 22008 KB Output is correct
19 Correct 902 ms 115192 KB Output is correct
20 Correct 911 ms 112548 KB Output is correct
21 Correct 881 ms 115064 KB Output is correct
22 Correct 903 ms 112632 KB Output is correct
23 Correct 897 ms 112632 KB Output is correct
24 Correct 908 ms 112632 KB Output is correct
25 Correct 901 ms 112684 KB Output is correct
26 Correct 924 ms 115164 KB Output is correct
27 Correct 920 ms 115140 KB Output is correct
28 Correct 913 ms 112504 KB Output is correct
29 Correct 906 ms 112508 KB Output is correct
30 Correct 887 ms 112632 KB Output is correct