oj.uz

Submission #894050

# Submission time Handle Problem Language Result Execution time Memory
894050 2023-12-27T21:32:55 Z raul2008487 Wall (IOI14_wall) C++17
61 / 100
 648 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 = 1000000000;
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 upmin(ll v, ll tl, ll tr, ll l, ll r, ll val){
    if(max(l, tl) > min(r, tr)){return ;}
    push(v, tl, tr);
    if(tl >= l && tr <= r){
        if(!last[v]){
            st[v] = {0ll, val};
            push(v, tl, tr);
        }
        else{
            st[v][0] = min(st[v][0], val);
            st[v][1] = min(st[v][1], val);
        }
        return ;
    }
    ll tm = (tl+tr)>>1;
    upmin(v*2, tl, tm, l, r, val);
    upmin(v*2+1, tm+1, tr, l, r, val);
}
void upmax(ll v, ll tl, ll tr, ll l, ll r, ll val){
    if(max(l, tl) > min(r, tr)){return ;}
    push(v, tl, tr);
    if(tl >= l && tr <= r){
        if(!last[v]){
            st[v] = {val, dh};
            push(v, tl, tr);
        }
        else{
            st[v][0] = max(st[v][0], val);
            st[v][1] = max(st[v][1], val);
        }
        return ;
    }
    ll tm = (tl+tr)>>1;
    upmax(v*2, tl, tm, l, r, val);
    upmax(v*2+1, tm+1, tr, l, r, val);
}
void build(ll v, ll l, ll r){
    if(l == r){
        last[v] = 1;
        res[v] = {0ll, 0ll};
        return ;
    }
    ll m = (l + r)>>1;
    build(v*2, l, m);
    build(v*2+1, m+1, r);
}
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] = {0ll, dh};
    }
    build(1, 0, n-1);
    for(i=0;i<k;i++){
        if(op[i] == 1){
            upmax(1, 0, n-1, left[i], right[i], height[i]);
        }
        else{
            upmin(1, 0, n-1, left[i], right[i], height[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:89:11: warning: unused variable 'j' [-Wunused-variable]
   89 |     ll i, j, z = 0;
      |           ^
wall.cpp:89:14: warning: unused variable 'z' [-Wunused-variable]
   89 |     ll i, j, z = 0;
      |              ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 250700 KB Output is correct
2 Correct 36 ms 250964 KB Output is correct
3 Correct 37 ms 250708 KB Output is correct
4 Correct 40 ms 250964 KB Output is correct
5 Correct 38 ms 250964 KB Output is correct
6 Correct 39 ms 251052 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 250788 KB Output is correct
2 Correct 134 ms 258640 KB Output is correct
3 Correct 176 ms 254292 KB Output is correct
4 Correct 428 ms 261496 KB Output is correct
5 Correct 249 ms 261972 KB Output is correct
6 Correct 253 ms 261884 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 250724 KB Output is correct
2 Correct 37 ms 250784 KB Output is correct
3 Correct 37 ms 250972 KB Output is correct
4 Correct 41 ms 250996 KB Output is correct
5 Correct 41 ms 250964 KB Output is correct
6 Correct 40 ms 250956 KB Output is correct
7 Correct 36 ms 250768 KB Output is correct
8 Correct 137 ms 258640 KB Output is correct
9 Correct 174 ms 254356 KB Output is correct
10 Correct 423 ms 261456 KB Output is correct
11 Correct 259 ms 261832 KB Output is correct
12 Correct 248 ms 262008 KB Output is correct
13 Correct 36 ms 250904 KB Output is correct
14 Correct 133 ms 258644 KB Output is correct
15 Correct 66 ms 251476 KB Output is correct
16 Correct 594 ms 261712 KB Output is correct
17 Correct 282 ms 261716 KB Output is correct
18 Correct 255 ms 261716 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 250716 KB Output is correct
2 Correct 37 ms 250956 KB Output is correct
3 Correct 37 ms 250904 KB Output is correct
4 Correct 41 ms 251220 KB Output is correct
5 Correct 40 ms 250960 KB Output is correct
6 Correct 41 ms 250960 KB Output is correct
7 Correct 36 ms 250836 KB Output is correct
8 Correct 132 ms 258768 KB Output is correct
9 Correct 174 ms 254288 KB Output is correct
10 Correct 422 ms 261440 KB Output is correct
11 Correct 283 ms 262092 KB Output is correct
12 Correct 242 ms 261968 KB Output is correct
13 Correct 35 ms 250708 KB Output is correct
14 Correct 142 ms 258640 KB Output is correct
15 Correct 65 ms 251468 KB Output is correct
16 Correct 648 ms 261928 KB Output is correct
17 Correct 248 ms 261700 KB Output is correct
18 Correct 251 ms 261716 KB Output is correct
19 Runtime error 492 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -