oj.uz

Submission #442484

# Submission time Handle Problem Language Result Execution time Memory
442484 2021-07-07T21:38:53 Z SirCovidThe19th Wall (IOI14_wall) C++14
100 / 100
 781 ms 102388 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

const int mx = (1<<22);

int N; pair<int, int> seg[mx*2]; // f - lowest, s - highest

void comb(int i, int l, int h){
    seg[i].f = min(seg[i].f, l); seg[i].s = max(min(seg[i].s, l), h);
}
void push(int i){ 
    comb(i*2, seg[i].f, seg[i].s), comb(i*2+1, seg[i].f, seg[i].s);
    seg[i] = {1e6, 0};
}
void upd(int x, int y, int op, int v, int l, int r, int i = 1){ 
    if (l > y or r < x) return;
    if (l >= x and r <= y){ comb(i, ((op == 2) ? v : 1e6), ((op == 1) ? v : 0)); return; }
    push(i); int m = (l+r)/2; 
    upd(x, y, op, v, l, m, i*2); upd(x, y, op, v, m+1, r, i*2+1); 
}
void solve(int* res, int l, int r, int i = 1){
    if (l == r){ res[l] = seg[i].s; return;  }
    push(i);
    int m = (l+r)/2; solve(res, l, m, i*2); solve(res, m+1, r, i*2+1); 
}   
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int res[]){
    fill(seg, seg+mx*2, make_pair(1e6, 0));
    for (int i = 0; i < k; i++) upd(l[i], r[i], op[i], h[i], 0, n-1);
    solve(res, 0, n-1);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65860 KB Output is correct
2 Correct 37 ms 65968 KB Output is correct
3 Correct 37 ms 65868 KB Output is correct
4 Correct 41 ms 66136 KB Output is correct
5 Correct 40 ms 66116 KB Output is correct
6 Correct 41 ms 66116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 65908 KB Output is correct
2 Correct 188 ms 73800 KB Output is correct
3 Correct 208 ms 69360 KB Output is correct
4 Correct 511 ms 83924 KB Output is correct
5 Correct 355 ms 85000 KB Output is correct
6 Correct 344 ms 83524 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 65868 KB Output is correct
2 Correct 38 ms 65988 KB Output is correct
3 Correct 37 ms 65932 KB Output is correct
4 Correct 41 ms 66076 KB Output is correct
5 Correct 41 ms 66084 KB Output is correct
6 Correct 41 ms 66116 KB Output is correct
7 Correct 36 ms 65948 KB Output is correct
8 Correct 191 ms 79520 KB Output is correct
9 Correct 210 ms 73092 KB Output is correct
10 Correct 516 ms 83976 KB Output is correct
11 Correct 349 ms 84932 KB Output is correct
12 Correct 345 ms 83396 KB Output is correct
13 Correct 36 ms 65868 KB Output is correct
14 Correct 196 ms 79500 KB Output is correct
15 Correct 64 ms 67120 KB Output is correct
16 Correct 520 ms 84132 KB Output is correct
17 Correct 350 ms 83684 KB Output is correct
18 Correct 339 ms 83560 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65860 KB Output is correct
2 Correct 38 ms 65972 KB Output is correct
3 Correct 38 ms 65848 KB Output is correct
4 Correct 42 ms 66116 KB Output is correct
5 Correct 43 ms 66248 KB Output is correct
6 Correct 41 ms 66080 KB Output is correct
7 Correct 36 ms 65860 KB Output is correct
8 Correct 193 ms 79532 KB Output is correct
9 Correct 209 ms 73036 KB Output is correct
10 Correct 513 ms 83900 KB Output is correct
11 Correct 348 ms 85096 KB Output is correct
12 Correct 352 ms 83504 KB Output is correct
13 Correct 36 ms 65872 KB Output is correct
14 Correct 193 ms 79540 KB Output is correct
15 Correct 65 ms 67076 KB Output is correct
16 Correct 519 ms 84220 KB Output is correct
17 Correct 349 ms 83652 KB Output is correct
18 Correct 345 ms 83652 KB Output is correct
19 Correct 781 ms 102280 KB Output is correct
20 Correct 760 ms 99708 KB Output is correct
21 Correct 768 ms 102224 KB Output is correct
22 Correct 770 ms 99748 KB Output is correct
23 Correct 758 ms 99900 KB Output is correct
24 Correct 756 ms 99884 KB Output is correct
25 Correct 756 ms 99976 KB Output is correct
26 Correct 766 ms 102272 KB Output is correct
27 Correct 759 ms 102388 KB Output is correct
28 Correct 752 ms 99780 KB Output is correct
29 Correct 756 ms 99808 KB Output is correct
30 Correct 750 ms 99912 KB Output is correct