oj.uz

Submission #297637

# Submission time Handle Problem Language Result Execution time Memory
297637 2020-09-11T16:59:42 Z juckter Wall (IOI14_wall) C++14
100 / 100
 990 ms 224740 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct node {
    int l, r, mx, mn;
    node *left, *right;

    void compose(int _mx, int _mn) {
        if(_mx > mn)
            mn = _mx;
        if(_mn < mx)
            mx = _mn;
        mx = max(mx, _mx);
        mn = min(mn, _mn);
    }

    void push() {
        left->compose(mx, mn);
        right->compose(mx, mn);
        mx = 0;
        mn = INF;
    }

    node(int l, int r) : l(l), r(r), mx(0), mn(INF) {
        if(l < r) {
            int m = (l + r) / 2;
            left = new node(l, m);
            right = new node(m + 1, r);
        }
    }

    void upd(int rl, int rr, int mn, int mx) {
        if(rr < l || r < rl)
            return;
        if(rl <= l && r <= rr) {
            compose(mx, mn);
            return;
        }
        push();
        left->upd(rl, rr, mn, mx);
        right->upd(rl, rr, mn, mx);
    }

    void trav(int* fi) {
        if(l == r)
            fi[l] = mx;
        else {
            push();
            left->trav(fi);
            right->trav(fi);
        }
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    node tree(0, n - 1);
    for(int i = 0; i < k; i++) {
        if(op[i] == 1)
            tree.upd(left[i], right[i], INF, height[i]);
        else
            tree.upd(left[i], right[i], height[i], 0);
    }

    tree.trav(finalHeight);

    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1536 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 6 ms 1536 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 176 ms 12152 KB Output is correct
3 Correct 205 ms 9208 KB Output is correct
4 Correct 689 ms 22264 KB Output is correct
5 Correct 320 ms 22520 KB Output is correct
6 Correct 315 ms 22520 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 7 ms 1536 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 6 ms 1536 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 166 ms 13980 KB Output is correct
9 Correct 193 ms 9208 KB Output is correct
10 Correct 689 ms 27724 KB Output is correct
11 Correct 333 ms 28920 KB Output is correct
12 Correct 322 ms 27256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 176 ms 13944 KB Output is correct
15 Correct 43 ms 3192 KB Output is correct
16 Correct 752 ms 28024 KB Output is correct
17 Correct 325 ms 27512 KB Output is correct
18 Correct 320 ms 27388 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 1536 KB Output is correct
5 Correct 6 ms 1536 KB Output is correct
6 Correct 7 ms 1536 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 166 ms 13944 KB Output is correct
9 Correct 194 ms 9208 KB Output is correct
10 Correct 701 ms 27768 KB Output is correct
11 Correct 336 ms 28792 KB Output is correct
12 Correct 317 ms 27256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 176 ms 13944 KB Output is correct
15 Correct 34 ms 3200 KB Output is correct
16 Correct 740 ms 28024 KB Output is correct
17 Correct 329 ms 27512 KB Output is correct
18 Correct 331 ms 27512 KB Output is correct
19 Correct 976 ms 224740 KB Output is correct
20 Correct 965 ms 222328 KB Output is correct
21 Correct 988 ms 224632 KB Output is correct
22 Correct 976 ms 222328 KB Output is correct
23 Correct 985 ms 222108 KB Output is correct
24 Correct 984 ms 222136 KB Output is correct
25 Correct 979 ms 222292 KB Output is correct
26 Correct 975 ms 224632 KB Output is correct
27 Correct 970 ms 224632 KB Output is correct
28 Correct 990 ms 222192 KB Output is correct
29 Correct 981 ms 222216 KB Output is correct
30 Correct 958 ms 222104 KB Output is correct