oj.uz

Submission #581437

# Submission time Handle Problem Language Result Execution time Memory
581437 2022-06-22T16:11:00 Z alirezasamimi100 Wall (IOI14_wall) C++17
100 / 100
 701 ms 156120 KB 
#include "wall.h"
#include <bits/stdc++.h>

#define pb push_back
#define lc v << 1
#define rc v << 1 | 1

using namespace std;

const int N = 2e6 + 10, inf = 1.05e9;

int n, k, fl[N], fr[N];
vector<int> L[N], R[N];

void build(int v, int l, int r){
    fl[v] = 0;
    fr[v] = inf;
    if(r - l > 1){
        int m = (l + r) >> 1;
        build(lc, l, m);
        build(rc, m, r);
    }
}

void upd(int v, int l, int r, int p, int lh, int rh){
    if(r - l == 1){
        fl[v] = lh;
        fr[v] = rh;
        return;
    }
    int m = (l + r) >> 1;
    if(p < m) upd(lc, l, m, p, lh, rh);
    else upd(rc, m, r, p, lh, rh);
    fl[v] = fl[lc];
    if(fl[rc] > fl[v]) fl[v] = fl[rc];
    if(fr[rc] < fl[v]) fl[v] = fr[rc];
    fr[v] = fr[lc];
    if(fr[rc] < fr[v]) fr[v] = fr[rc];
    if(fl[rc] > fr[v]) fr[v] = fl[rc];
}

void buildWall(int wtn, int wtk, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = wtn;
    k = wtk;
    int LH[k],RH[k];
    for(int i = 0; i < k; i++){
        L[left[i]].pb(i);
        R[right[i]].pb(i);
        if(op[i] == 1){
            LH[i] = height[i];
            RH[i] = inf;
        }else{
            LH[i] = 0;
            RH[i] = height[i];
        }
    }
    build(1, 0, k);
    for(int i = 0; i < n; i++){
        for(int j : L[i]) upd(1, 0, k, j, LH[j], RH[j]);
        finalHeight[i] = fl[1];
        for(int j : R[i]) upd(1, 0, k, j, 0, inf);
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94228 KB Output is correct
2 Correct 56 ms 94576 KB Output is correct
3 Correct 47 ms 94312 KB Output is correct
4 Correct 53 ms 94768 KB Output is correct
5 Correct 49 ms 94796 KB Output is correct
6 Correct 51 ms 94792 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94172 KB Output is correct
2 Correct 324 ms 118404 KB Output is correct
3 Correct 253 ms 106732 KB Output is correct
4 Correct 701 ms 124412 KB Output is correct
5 Correct 358 ms 122888 KB Output is correct
6 Correct 349 ms 122480 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94120 KB Output is correct
2 Correct 49 ms 94480 KB Output is correct
3 Correct 49 ms 94296 KB Output is correct
4 Correct 52 ms 94776 KB Output is correct
5 Correct 50 ms 94792 KB Output is correct
6 Correct 52 ms 94792 KB Output is correct
7 Correct 47 ms 94232 KB Output is correct
8 Correct 315 ms 118356 KB Output is correct
9 Correct 254 ms 106612 KB Output is correct
10 Correct 682 ms 124540 KB Output is correct
11 Correct 356 ms 122748 KB Output is correct
12 Correct 360 ms 122428 KB Output is correct
13 Correct 47 ms 94196 KB Output is correct
14 Correct 330 ms 118380 KB Output is correct
15 Correct 77 ms 96528 KB Output is correct
16 Correct 696 ms 124536 KB Output is correct
17 Correct 408 ms 122164 KB Output is correct
18 Correct 390 ms 121804 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 94204 KB Output is correct
2 Correct 53 ms 94584 KB Output is correct
3 Correct 49 ms 94348 KB Output is correct
4 Correct 53 ms 94796 KB Output is correct
5 Correct 52 ms 94796 KB Output is correct
6 Correct 53 ms 94760 KB Output is correct
7 Correct 48 ms 94204 KB Output is correct
8 Correct 336 ms 118400 KB Output is correct
9 Correct 246 ms 106696 KB Output is correct
10 Correct 683 ms 124364 KB Output is correct
11 Correct 355 ms 122700 KB Output is correct
12 Correct 359 ms 122492 KB Output is correct
13 Correct 51 ms 94300 KB Output is correct
14 Correct 341 ms 118448 KB Output is correct
15 Correct 77 ms 96460 KB Output is correct
16 Correct 695 ms 124580 KB Output is correct
17 Correct 391 ms 122212 KB Output is correct
18 Correct 399 ms 121944 KB Output is correct
19 Correct 601 ms 156120 KB Output is correct
20 Correct 604 ms 153576 KB Output is correct
21 Correct 616 ms 155908 KB Output is correct
22 Correct 596 ms 153588 KB Output is correct
23 Correct 607 ms 153396 KB Output is correct
24 Correct 594 ms 153612 KB Output is correct
25 Correct 626 ms 153620 KB Output is correct
26 Correct 625 ms 155996 KB Output is correct
27 Correct 615 ms 156052 KB Output is correct
28 Correct 608 ms 153388 KB Output is correct
29 Correct 610 ms 153540 KB Output is correct
30 Correct 601 ms 153588 KB Output is correct