oj.uz

Submission #894582

# Submission time Handle Problem Language Result Execution time Memory
894582 2023-12-28T13:20:42 Z raul2008487 Wall (IOI14_wall) C++17
100 / 100
 585 ms 177636 KB 
/* R */
#include<bits/stdc++.h>
#include "wall.h"
#define ll long long
#define vl vector<ll>
#define pll pair<ll,ll>
#define in insert
#define fi first
#define se second
#define all(v) v.begin(), v.end()
using namespace std;
const ll sz = 2e6+6;
const ll inf = 1000000000000000;
vector<array<ll, 2>> st;
ll res[sz];
void comp(ll x1, ll x2){
    st[x2][0] = min(st[x1][1], max(st[x2][0], st[x1][0]));
    st[x2][1] = max(st[x1][0], min(st[x2][1], st[x1][1]));
}
void push(ll v, ll l, ll r){
    if(l == r){return ;}
    comp(v, v*2);
    comp(v, v*2+1);
    st[v] = {0, inf};
}
void update(ll v, ll tl, ll tr, ll l, ll r, ll val, ll  type){
    if(tl > r || tr <l){return ;}
    if(tl >= l && tr <= r){
        if(type == 1){
            st[v][0] = max(st[v][0], val);
            st[v][1] = max(st[v][1], val);
        }
        else{
            st[v][0] = min(st[v][0], val);
            st[v][1] = min(st[v][1], val);
        }
        return ;
    }
    push(v, tl, tr);
    ll tm = (tl+tr)>>1;
    update(v*2, tl, tm, l, r, val, type);
    update(v*2+1, tm+1, tr, l, r, val, type);
}
void trav(ll v, ll tl, ll tr){
    if(tl == tr){
        res[tl - 1] = st[v][0];
        return ;
    }
    push(v, tl, tr);
    ll tm = (tl + tr)>>1;
    trav(v*2, tl, tm);
    trav(v*2+1, tm+1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    ll i, j, z = 0;
    st.assign(sz*4, {0, inf});
    for(i=0;i<k;i++){
        update(1, 1, n, left[i] + 1, right[i] + 1, height[i], op[i]);
    }
    trav(1, 1, n);
    for(i=0;i<n;i++){
        //cout << res[i] << ' ';
        finalHeight[i] = max(z, res[i]);
    }
}

/*
10 6
1 1 8 4
0 4 9 1
0 3 6 5
1 0 5 3
1 2 2 5
0 6 7 0

*/

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:55:11: warning: unused variable 'j' [-Wunused-variable]
   55 |     ll i, j, z = 0;
      |           ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 125520 KB Output is correct
2 Correct 20 ms 125784 KB Output is correct
3 Correct 19 ms 125784 KB Output is correct
4 Correct 26 ms 125780 KB Output is correct
5 Correct 21 ms 125776 KB Output is correct
6 Correct 21 ms 126000 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 125532 KB Output is correct
2 Correct 120 ms 139168 KB Output is correct
3 Correct 134 ms 132768 KB Output is correct
4 Correct 340 ms 145788 KB Output is correct
5 Correct 226 ms 146768 KB Output is correct
6 Correct 221 ms 145232 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 125728 KB Output is correct
2 Correct 19 ms 125776 KB Output is correct
3 Correct 19 ms 125528 KB Output is correct
4 Correct 24 ms 125780 KB Output is correct
5 Correct 22 ms 125776 KB Output is correct
6 Correct 21 ms 125828 KB Output is correct
7 Correct 22 ms 125516 KB Output is correct
8 Correct 115 ms 139092 KB Output is correct
9 Correct 135 ms 132796 KB Output is correct
10 Correct 344 ms 145880 KB Output is correct
11 Correct 238 ms 146892 KB Output is correct
12 Correct 223 ms 145188 KB Output is correct
13 Correct 18 ms 125520 KB Output is correct
14 Correct 117 ms 139268 KB Output is correct
15 Correct 36 ms 126800 KB Output is correct
16 Correct 348 ms 146000 KB Output is correct
17 Correct 231 ms 145364 KB Output is correct
18 Correct 230 ms 145576 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 125528 KB Output is correct
2 Correct 19 ms 125784 KB Output is correct
3 Correct 19 ms 125528 KB Output is correct
4 Correct 22 ms 125788 KB Output is correct
5 Correct 24 ms 125788 KB Output is correct
6 Correct 22 ms 125832 KB Output is correct
7 Correct 18 ms 125580 KB Output is correct
8 Correct 115 ms 139184 KB Output is correct
9 Correct 135 ms 132872 KB Output is correct
10 Correct 352 ms 145940 KB Output is correct
11 Correct 227 ms 146748 KB Output is correct
12 Correct 224 ms 145232 KB Output is correct
13 Correct 19 ms 125632 KB Output is correct
14 Correct 118 ms 139084 KB Output is correct
15 Correct 37 ms 126796 KB Output is correct
16 Correct 395 ms 146256 KB Output is correct
17 Correct 241 ms 145392 KB Output is correct
18 Correct 239 ms 145424 KB Output is correct
19 Correct 500 ms 177636 KB Output is correct
20 Correct 500 ms 175188 KB Output is correct
21 Correct 497 ms 177524 KB Output is correct
22 Correct 493 ms 175044 KB Output is correct
23 Correct 544 ms 175192 KB Output is correct
24 Correct 509 ms 175184 KB Output is correct
25 Correct 499 ms 175112 KB Output is correct
26 Correct 585 ms 177628 KB Output is correct
27 Correct 502 ms 177492 KB Output is correct
28 Correct 539 ms 175184 KB Output is correct
29 Correct 485 ms 175196 KB Output is correct
30 Correct 528 ms 175056 KB Output is correct