oj.uz

Submission #566044

# Submission time Handle Problem Language Result Execution time Memory
566044 2022-05-21T17:16:39 Z Leo121 Wall (IOI14_wall) C++14
100 / 100
 654 ms 77356 KB 
#include <bits/stdc++.h>
#include "wall.h"

#define for0(i, n) for(int i = 0; i < int(b); ++ i)
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2e6;
pii st[4 * maxn + 1];
int valu[maxn];

void built(int nodo, int l, int r){
    st[nodo] = mp(0, 0);
    if(l == r){
        return;
    }
    int mitad = (l + r) / 2;
    built(nodo * 2, l, mitad);
    built(nodo * 2 + 1, mitad + 1, r);
}

void update(int nodo, int l, int r, int a, int b, bool tipo, int val){
    if(l != r && st[nodo].fi == st[nodo].se){
        st[nodo * 2] = st[nodo];
        st[nodo * 2 + 1] = st[nodo];
    }
    if(r < a || l > b){
        return;
    }
    if(l >= a && r <= b){
        if(tipo){
            if(st[nodo].se >= val){
                return;
            }
            if(st[nodo].fi < val){
                st[nodo] = mp(val, val);
                return;
            }
        }
        else{
            if(st[nodo].fi <= val){
                return;
            }
            if(st[nodo].se > val){
                st[nodo] = mp(val, val);
                return;
            }
        }
    }
    int mitad = (l + r) / 2;
    update(nodo * 2, l, mitad, a, b, tipo, val);
    update(nodo * 2 + 1, mitad + 1, r, a, b, tipo, val);
    st[nodo] = mp(max(st[nodo * 2].fi, st[nodo * 2 + 1].fi), min(st[nodo * 2].se, st[nodo * 2 + 1].se));
}

void query(int nodo, int l, int r){
    if(st[nodo].fi == st[nodo].se){
        forn(i, l, r){
            valu[i] = st[nodo].fi;
        }
        return;
    }
    int mitad = (l + r) / 2;
    query(nodo * 2, l, mitad);
    query(nodo * 2 + 1, mitad + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    built(1, 0, n - 1);
    for(int i = 0; i < k; ++ i){
        bool opcion = (op[i] == 1);
        update(1, 0, n - 1, left[i], right[i], opcion, height[i]);
    }
    query(1, 0, n - 1);
    for(int i = 0; i < n; ++ i){
        finalHeight[i] = valu[i];
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 131 ms 8124 KB Output is correct
3 Correct 168 ms 4300 KB Output is correct
4 Correct 440 ms 20728 KB Output is correct
5 Correct 318 ms 21804 KB Output is correct
6 Correct 295 ms 20296 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 5 ms 668 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 146 ms 8056 KB Output is correct
9 Correct 162 ms 4268 KB Output is correct
10 Correct 402 ms 20720 KB Output is correct
11 Correct 296 ms 21864 KB Output is correct
12 Correct 278 ms 20268 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 143 ms 13844 KB Output is correct
15 Correct 31 ms 2012 KB Output is correct
16 Correct 521 ms 20936 KB Output is correct
17 Correct 286 ms 20424 KB Output is correct
18 Correct 271 ms 20380 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 133 ms 8140 KB Output is correct
9 Correct 149 ms 4172 KB Output is correct
10 Correct 439 ms 20700 KB Output is correct
11 Correct 321 ms 21764 KB Output is correct
12 Correct 284 ms 20320 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 136 ms 13904 KB Output is correct
15 Correct 31 ms 2008 KB Output is correct
16 Correct 528 ms 21068 KB Output is correct
17 Correct 277 ms 20460 KB Output is correct
18 Correct 277 ms 20500 KB Output is correct
19 Correct 635 ms 77312 KB Output is correct
20 Correct 634 ms 74820 KB Output is correct
21 Correct 619 ms 77356 KB Output is correct
22 Correct 624 ms 74944 KB Output is correct
23 Correct 619 ms 74792 KB Output is correct
24 Correct 622 ms 74732 KB Output is correct
25 Correct 627 ms 74832 KB Output is correct
26 Correct 654 ms 77356 KB Output is correct
27 Correct 623 ms 77320 KB Output is correct
28 Correct 632 ms 74924 KB Output is correct
29 Correct 629 ms 74836 KB Output is correct
30 Correct 625 ms 74868 KB Output is correct