oj.uz

Submission #894049

# Submission time Handle Problem Language Result Execution time Memory
894049 2023-12-27T21:10:02 Z raul2008487 Wall (IOI14_wall) C++17
61 / 100
 658 ms 262144 KB 
#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 dh = 1e9;
vector<array<ll, 2>> st(sz*4), res(sz*4);
bool last[sz*4];
void comp(ll x1, ll x2){
    if(st[x1][0] > st[x2][1]){
        st[x2] = {st[x1][0], st[x1][0]};
    }
    else if(st[x1][1] < st[x2][0]){
        st[x2] = {st[x1][1], st[x1][1]};
    }
    else{
        st[x2] = {max(st[x1][0], st[x2][0]), min(st[x1][1], st[x2][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, dh};
}
void build(ll v, ll l, ll r){
    if(l == r){
        last[v] = 1;
        res[v] = {0, 0};
        return ;
    }
    ll m = (l + r)>>1;
    build(v*2, l, m);
    build(v*2+1, m+1, r);
}
void update(ll v, ll tl, ll tr, ll l, ll r, ll val, ll  type){
    if(max(l, tl) > min(r, tr)){return ;}
    push(v, tl, tr);
    if(tl >= l && tr <= r){
        if(tl == tr){
            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 ;
        }
        if(type == 1){
            st[v] = {val, dh};
        }
        else{
            st[v] = {0, val};
        }
        push(v, tl, tr);
        return ;
    }
    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] = st[v];
        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;
    for(i=0;i<=(n<<2);i++){
        st[i] = {0, dh};
    }
    build(1, 0, n-1);
    for(i=0;i<k;i++){
        update(1, 0, n-1, left[i], right[i], height[i], op[i]);
    }
    trav(1, 0, n-1);
    for(i=0;i<n;i++){
        finalHeight[i] = res[i][0];
    }
}

/*
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:81:11: warning: unused variable 'j' [-Wunused-variable]
   81 |     ll i, j, z = 0;
      |           ^
wall.cpp:81:14: warning: unused variable 'z' [-Wunused-variable]
   81 |     ll i, j, z = 0;
      |              ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 250896 KB Output is correct
2 Correct 40 ms 250796 KB Output is correct
3 Correct 37 ms 250972 KB Output is correct
4 Correct 40 ms 250964 KB Output is correct
5 Correct 39 ms 250972 KB Output is correct
6 Correct 38 ms 250968 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 250704 KB Output is correct
2 Correct 146 ms 258648 KB Output is correct
3 Correct 168 ms 254292 KB Output is correct
4 Correct 419 ms 261444 KB Output is correct
5 Correct 249 ms 261972 KB Output is correct
6 Correct 259 ms 261984 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 250708 KB Output is correct
2 Correct 37 ms 250960 KB Output is correct
3 Correct 36 ms 250704 KB Output is correct
4 Correct 42 ms 250880 KB Output is correct
5 Correct 39 ms 250956 KB Output is correct
6 Correct 39 ms 251052 KB Output is correct
7 Correct 38 ms 250704 KB Output is correct
8 Correct 144 ms 258640 KB Output is correct
9 Correct 168 ms 254288 KB Output is correct
10 Correct 414 ms 261524 KB Output is correct
11 Correct 252 ms 261808 KB Output is correct
12 Correct 264 ms 261956 KB Output is correct
13 Correct 36 ms 250704 KB Output is correct
14 Correct 146 ms 258644 KB Output is correct
15 Correct 65 ms 251476 KB Output is correct
16 Correct 610 ms 261652 KB Output is correct
17 Correct 268 ms 261660 KB Output is correct
18 Correct 254 ms 261712 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 250684 KB Output is correct
2 Correct 36 ms 250968 KB Output is correct
3 Correct 35 ms 250968 KB Output is correct
4 Correct 41 ms 250912 KB Output is correct
5 Correct 39 ms 251352 KB Output is correct
6 Correct 39 ms 250972 KB Output is correct
7 Correct 36 ms 250856 KB Output is correct
8 Correct 143 ms 258668 KB Output is correct
9 Correct 177 ms 254292 KB Output is correct
10 Correct 423 ms 261456 KB Output is correct
11 Correct 252 ms 261968 KB Output is correct
12 Correct 247 ms 261776 KB Output is correct
13 Correct 35 ms 250716 KB Output is correct
14 Correct 185 ms 258692 KB Output is correct
15 Correct 66 ms 251472 KB Output is correct
16 Correct 658 ms 261640 KB Output is correct
17 Correct 263 ms 261708 KB Output is correct
18 Correct 257 ms 261760 KB Output is correct
19 Runtime error 477 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -