oj.uz

Submission #403332

# Submission time Handle Problem Language Result Execution time Memory
403332 2021-05-13T04:01:44 Z danielcm585 Wall (IOI14_wall) C++14
100 / 100
 1048 ms 224648 KB 
#include "wall.h"

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct ops {
    int mn, mx;

    ops(int x = INF, int y = -INF): mn(x), mx(y) {}

    ops operator + (ops v) {
        if (mn < v.mx) return ops(v.mx,v.mx);
        if (mx > v.mn) return ops(v.mn,v.mn);
        return ops(min(mn,v.mn),max(mx,v.mx));
    }
};

struct segTree {
    segTree *lf, *rg;
    int l, r;
    ops val;

    segTree(int x, int y) {
        l = x, r = y;
        val = ops(0,0);
    }

    void build() {
        if (l == r) return;
        int mid = (l+r)/2;
        lf = new segTree(l,mid); lf->build();
        rg = new segTree(mid+1,r); rg->build();
    }

    void prop() {
        lf->val = lf->val+val;
        rg->val = rg->val+val;
        val = ops();
    }

    void update(int x, int y, ops v) {
        if (l > y || r < x) return;
        if (l >= x && r <= y) {
            val = val+v;
            return;
        }
        prop();
        lf->update(x,y,v); rg->update(x,y,v);
    }

    void solve(int ans[]) {
        if (l == r) {
            ans[l] = val.mn;
            return;
        }
        prop();
        lf->solve(ans); rg->solve(ans);
    }

} *st;

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
    st = new segTree(0,n-1); st->build();
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) st->update(l[i],r[i],ops(INF,h[i]));
        else st->update(l[i],r[i],ops(h[i],-INF));
        // st->solve(ans);
        // for (int j = 0; j < n; j++) cout << ans[j] << ' ';
        // cout << '\n';
    }
    st->solve(ans);
}

/*
10 6
1 1 8 4
0 4 9 1
0 3 6 5
1 0 5 3
1 2 2 5
0 6 7 0
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 1484 KB Output is correct
5 Correct 7 ms 1384 KB Output is correct
6 Correct 7 ms 1484 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 180 ms 13992 KB Output is correct
3 Correct 181 ms 9144 KB Output is correct
4 Correct 620 ms 27628 KB Output is correct
5 Correct 309 ms 28720 KB Output is correct
6 Correct 367 ms 27156 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 10 ms 1460 KB Output is correct
5 Correct 7 ms 1484 KB Output is correct
6 Correct 7 ms 1484 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 152 ms 13956 KB Output is correct
9 Correct 196 ms 9072 KB Output is correct
10 Correct 595 ms 27704 KB Output is correct
11 Correct 316 ms 28752 KB Output is correct
12 Correct 323 ms 27244 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 170 ms 13992 KB Output is correct
15 Correct 40 ms 3092 KB Output is correct
16 Correct 768 ms 27916 KB Output is correct
17 Correct 315 ms 27292 KB Output is correct
18 Correct 357 ms 27424 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 9 ms 1432 KB Output is correct
5 Correct 7 ms 1484 KB Output is correct
6 Correct 7 ms 1432 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 152 ms 13908 KB Output is correct
9 Correct 177 ms 9084 KB Output is correct
10 Correct 589 ms 27740 KB Output is correct
11 Correct 304 ms 28740 KB Output is correct
12 Correct 317 ms 27168 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 158 ms 13912 KB Output is correct
15 Correct 41 ms 3088 KB Output is correct
16 Correct 719 ms 27940 KB Output is correct
17 Correct 321 ms 27332 KB Output is correct
18 Correct 342 ms 27384 KB Output is correct
19 Correct 966 ms 224500 KB Output is correct
20 Correct 953 ms 222000 KB Output is correct
21 Correct 946 ms 224508 KB Output is correct
22 Correct 938 ms 221956 KB Output is correct
23 Correct 959 ms 221960 KB Output is correct
24 Correct 927 ms 222060 KB Output is correct
25 Correct 930 ms 221944 KB Output is correct
26 Correct 966 ms 224648 KB Output is correct
27 Correct 981 ms 224532 KB Output is correct
28 Correct 955 ms 221964 KB Output is correct
29 Correct 1030 ms 221984 KB Output is correct
30 Correct 1048 ms 222044 KB Output is correct