oj.uz

Submission #122673

# Submission time Handle Problem Language Result Execution time Memory
122673 2019-06-29T06:31:49 Z arman_ferdous Wall (IOI14_wall) C++14
100 / 100
 767 ms 66956 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2e6+100;
const int oo = 1e9;

int n;
pair<int,int> t[N<<2];

int getHeight(pair<int,int> v, int init = 0) {
    return max(min(init, v.first), v.second);
}

void add(pair<int,int> &tmp, int h) {
    tmp.second = max(tmp.second, h);
    tmp.first = max(tmp.first, tmp.second);
}
void rem(pair<int,int> &tmp, int h) {
    tmp.first = min(tmp.first, h);
    tmp.second = min(tmp.first, tmp.second);
}

void shift(int node, int L, int R) {
    int lc = node << 1, rc = lc | 1;
    rem(t[lc], t[node].first);
    add(t[lc], t[node].second);
    rem(t[rc], t[node].first);
    add(t[rc], t[node].second);
    t[node] = {oo, 0};
}

void build(int node, int L, int R) {
    t[node] = {oo, 0};
    if(L == R) return;
    int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
    build(lc, L, mid); build(rc, mid + 1, R);
}

void upd(int node, int L, int R, int op, int l, int r, int h) {
    if(r < L || R < l) return;
    if(l <= L && R <= r) {
        if(op == 1) add(t[node], h);
        else rem(t[node], h);
        return;
    } shift(node, L, R);
    int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
    upd(lc, L, mid, op, l, r, h);
    upd(rc, mid + 1, R, op, l, r, h);
}

int soln[N];
void retrieve(int node, int L, int R) {
    if(L == R) return void(soln[L] = getHeight(t[node]));
    shift(node, L, R);
    int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
    retrieve(lc, L, mid); retrieve(rc, mid + 1, R);
}

void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = _n;
    build(1, 0, n - 1);
    for(int i = 0; i < k; i++)
        upd(1, 0, n - 1, op[i], left[i], right[i], height[i]);
    retrieve(1, 0, n - 1);
    for(int i = 0; i < n; i++)
        finalHeight[i] = soln[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 9 ms 760 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 7 ms 888 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 175 ms 8152 KB Output is correct
3 Correct 201 ms 4344 KB Output is correct
4 Correct 561 ms 11256 KB Output is correct
5 Correct 345 ms 11768 KB Output is correct
6 Correct 325 ms 11644 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 174 ms 8196 KB Output is correct
9 Correct 201 ms 4344 KB Output is correct
10 Correct 560 ms 11272 KB Output is correct
11 Correct 332 ms 11752 KB Output is correct
12 Correct 320 ms 11688 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 177 ms 8252 KB Output is correct
15 Correct 38 ms 1528 KB Output is correct
16 Correct 674 ms 11528 KB Output is correct
17 Correct 326 ms 11608 KB Output is correct
18 Correct 324 ms 11512 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 424 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 174 ms 8184 KB Output is correct
9 Correct 201 ms 4472 KB Output is correct
10 Correct 559 ms 11288 KB Output is correct
11 Correct 330 ms 11768 KB Output is correct
12 Correct 318 ms 11756 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 176 ms 8184 KB Output is correct
15 Correct 39 ms 1500 KB Output is correct
16 Correct 682 ms 11512 KB Output is correct
17 Correct 327 ms 11512 KB Output is correct
18 Correct 323 ms 11512 KB Output is correct
19 Correct 766 ms 66956 KB Output is correct
20 Correct 754 ms 64632 KB Output is correct
21 Correct 761 ms 66936 KB Output is correct
22 Correct 755 ms 64508 KB Output is correct
23 Correct 757 ms 64448 KB Output is correct
24 Correct 752 ms 64376 KB Output is correct
25 Correct 753 ms 64492 KB Output is correct
26 Correct 759 ms 66936 KB Output is correct
27 Correct 767 ms 66936 KB Output is correct
28 Correct 755 ms 64476 KB Output is correct
29 Correct 763 ms 64540 KB Output is correct
30 Correct 763 ms 64504 KB Output is correct