oj.uz

Submission #113591

# Submission time Handle Problem Language Result Execution time Memory
113591 2019-05-26T13:44:49 Z nvmdava Wall (IOI14_wall) C++17
100 / 100
 784 ms 77764 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define N 2097152
#define inf 100005
struct Query{
    int l, r;
};

Query lazy[N << 1];
int tree[N << 1];

void push(int id){
    if(id >= N){
        tree[id] = min(tree[id], lazy[id].r);
        tree[id] = max(tree[id], lazy[id].l);
    } else {
        if(lazy[id << 1].r <= lazy[id].l){
            lazy[id << 1].l = lazy[id].l;
            lazy[id << 1].r = lazy[id].l;
        } else if(lazy[id << 1].l >= lazy[id].r){
            lazy[id << 1].l = lazy[id].r;
            lazy[id << 1].r = lazy[id].r;
        } else {
            lazy[id << 1].l = max(lazy[id << 1].l, lazy[id].l);
            lazy[id << 1].r = min(lazy[id << 1].r, lazy[id].r);
        }
        if(lazy[id << 1 | 1].r <= lazy[id].l){
            lazy[id << 1 | 1].l = lazy[id].l;
            lazy[id << 1 | 1].r = lazy[id].l;
        } else if(lazy[id << 1 | 1].l >= lazy[id].r){
            lazy[id << 1 | 1].l = lazy[id].r;
            lazy[id << 1 | 1].r = lazy[id].r;
        } else {
            lazy[id << 1 | 1].l = max(lazy[id << 1 | 1].l, lazy[id].l);
            lazy[id << 1 | 1].r = min(lazy[id << 1 | 1].r, lazy[id].r);
        }
    }
    lazy[id].l = 0;
    lazy[id].r = inf;
}

void update(int id, int l, int r, int L, int R, int vall, int valr){
    if(R < l || L > r) return;
    push(id);
    if(L <= l && r <= R){
        lazy[id].l = vall;
        lazy[id].r = valr;
    } else {
        int m = (l + r) >> 1;
        update(id << 1, l, m, L, R, vall, valr);
        update(id << 1 | 1, m + 1, r, L, R, vall ,valr);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0; i < k; i++){
        if(op[i] == 1)
            update(1, 1, N, left[i] + 1, right[i] + 1, height[i], inf);
        else
            update(1, 1, N, left[i] + 1, right[i] + 1, 0, height[i]);
    }
    for(int i = 1; i < N * 2; i++)
        push(i);
    for(int i = 0; i < n; i++){
        finalHeight[i] = tree[i + N];
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 41336 KB Output is correct
2 Correct 60 ms 41464 KB Output is correct
3 Correct 61 ms 41464 KB Output is correct
4 Correct 68 ms 41592 KB Output is correct
5 Correct 173 ms 41720 KB Output is correct
6 Correct 61 ms 41592 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 41464 KB Output is correct
2 Correct 474 ms 55148 KB Output is correct
3 Correct 246 ms 48528 KB Output is correct
4 Correct 614 ms 59512 KB Output is correct
5 Correct 370 ms 60392 KB Output is correct
6 Correct 349 ms 58824 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 41396 KB Output is correct
2 Correct 59 ms 41520 KB Output is correct
3 Correct 59 ms 41464 KB Output is correct
4 Correct 64 ms 41564 KB Output is correct
5 Correct 70 ms 41720 KB Output is correct
6 Correct 63 ms 41720 KB Output is correct
7 Correct 66 ms 41336 KB Output is correct
8 Correct 343 ms 55076 KB Output is correct
9 Correct 244 ms 48588 KB Output is correct
10 Correct 752 ms 59516 KB Output is correct
11 Correct 359 ms 60472 KB Output is correct
12 Correct 388 ms 58956 KB Output is correct
13 Correct 56 ms 41336 KB Output is correct
14 Correct 351 ms 55020 KB Output is correct
15 Correct 90 ms 42616 KB Output is correct
16 Correct 784 ms 59692 KB Output is correct
17 Correct 350 ms 59128 KB Output is correct
18 Correct 352 ms 59128 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 41336 KB Output is correct
2 Correct 58 ms 41496 KB Output is correct
3 Correct 56 ms 41464 KB Output is correct
4 Correct 63 ms 41724 KB Output is correct
5 Correct 61 ms 41720 KB Output is correct
6 Correct 67 ms 41592 KB Output is correct
7 Correct 55 ms 41336 KB Output is correct
8 Correct 330 ms 55032 KB Output is correct
9 Correct 239 ms 48504 KB Output is correct
10 Correct 572 ms 59440 KB Output is correct
11 Correct 336 ms 60552 KB Output is correct
12 Correct 336 ms 58872 KB Output is correct
13 Correct 55 ms 41464 KB Output is correct
14 Correct 322 ms 55132 KB Output is correct
15 Correct 91 ms 42616 KB Output is correct
16 Correct 759 ms 59768 KB Output is correct
17 Correct 347 ms 59128 KB Output is correct
18 Correct 349 ms 59128 KB Output is correct
19 Correct 654 ms 77676 KB Output is correct
20 Correct 644 ms 75244 KB Output is correct
21 Correct 653 ms 77572 KB Output is correct
22 Correct 702 ms 75108 KB Output is correct
23 Correct 678 ms 75224 KB Output is correct
24 Correct 656 ms 75164 KB Output is correct
25 Correct 693 ms 75268 KB Output is correct
26 Correct 690 ms 77764 KB Output is correct
27 Correct 687 ms 77724 KB Output is correct
28 Correct 681 ms 75132 KB Output is correct
29 Correct 679 ms 75128 KB Output is correct
30 Correct 668 ms 75136 KB Output is correct