oj.uz

Submission #894042

# Submission time Handle Problem Language Result Execution time Memory
894042 2023-12-27T20:49:25 Z raul2008487 Wall (IOI14_wall) C++17
61 / 100
 1265 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 int sz = 2e6+6;
const ll dh = 1e9;
vector<array<ll, 2>> st(sz<<2), res(sz);
bool last[sz];
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(last[v]){
            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 23 ms 156764 KB Output is correct
2 Correct 24 ms 157020 KB Output is correct
3 Correct 24 ms 157020 KB Output is correct
4 Correct 29 ms 157228 KB Output is correct
5 Correct 27 ms 157264 KB Output is correct
6 Correct 27 ms 157272 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 156764 KB Output is correct
2 Correct 125 ms 164764 KB Output is correct
3 Correct 164 ms 160360 KB Output is correct
4 Correct 440 ms 174996 KB Output is correct
5 Correct 240 ms 176224 KB Output is correct
6 Correct 251 ms 174656 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 156928 KB Output is correct
2 Correct 24 ms 156860 KB Output is correct
3 Correct 23 ms 157020 KB Output is correct
4 Correct 28 ms 157264 KB Output is correct
5 Correct 26 ms 157264 KB Output is correct
6 Correct 26 ms 157040 KB Output is correct
7 Correct 23 ms 156760 KB Output is correct
8 Correct 128 ms 170572 KB Output is correct
9 Correct 159 ms 164140 KB Output is correct
10 Correct 408 ms 175128 KB Output is correct
11 Correct 243 ms 176220 KB Output is correct
12 Correct 282 ms 174472 KB Output is correct
13 Correct 23 ms 156756 KB Output is correct
14 Correct 132 ms 170752 KB Output is correct
15 Correct 52 ms 158040 KB Output is correct
16 Correct 593 ms 175352 KB Output is correct
17 Correct 244 ms 174676 KB Output is correct
18 Correct 242 ms 174900 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 156764 KB Output is correct
2 Correct 26 ms 157220 KB Output is correct
3 Correct 25 ms 157020 KB Output is correct
4 Correct 28 ms 157104 KB Output is correct
5 Correct 26 ms 157208 KB Output is correct
6 Correct 27 ms 157068 KB Output is correct
7 Correct 23 ms 156764 KB Output is correct
8 Correct 127 ms 170576 KB Output is correct
9 Correct 169 ms 164300 KB Output is correct
10 Correct 424 ms 175184 KB Output is correct
11 Correct 258 ms 176468 KB Output is correct
12 Correct 241 ms 174644 KB Output is correct
13 Correct 22 ms 156760 KB Output is correct
14 Correct 126 ms 170528 KB Output is correct
15 Correct 54 ms 158032 KB Output is correct
16 Correct 597 ms 175400 KB Output is correct
17 Correct 244 ms 174828 KB Output is correct
18 Correct 254 ms 174832 KB Output is correct
19 Runtime error 1265 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -