oj.uz

Submission #894045

# Submission time Handle Problem Language Result Execution time Memory
894045 2023-12-27T20:53:27 Z raul2008487 Wall (IOI14_wall) C++17
61 / 100
 654 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<<2);
bool last[sz<<2];
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 43 ms 250704 KB Output is correct
2 Correct 37 ms 250960 KB Output is correct
3 Correct 37 ms 250840 KB Output is correct
4 Correct 41 ms 250960 KB Output is correct
5 Correct 41 ms 250964 KB Output is correct
6 Correct 41 ms 251108 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 250704 KB Output is correct
2 Correct 133 ms 258700 KB Output is correct
3 Correct 180 ms 254292 KB Output is correct
4 Correct 415 ms 261452 KB Output is correct
5 Correct 248 ms 262064 KB Output is correct
6 Correct 249 ms 261956 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 250708 KB Output is correct
2 Correct 40 ms 250812 KB Output is correct
3 Correct 37 ms 250944 KB Output is correct
4 Correct 44 ms 251220 KB Output is correct
5 Correct 39 ms 250964 KB Output is correct
6 Correct 44 ms 251076 KB Output is correct
7 Correct 37 ms 250836 KB Output is correct
8 Correct 135 ms 258644 KB Output is correct
9 Correct 172 ms 254556 KB Output is correct
10 Correct 417 ms 261456 KB Output is correct
11 Correct 255 ms 261968 KB Output is correct
12 Correct 248 ms 261964 KB Output is correct
13 Correct 35 ms 250876 KB Output is correct
14 Correct 134 ms 258640 KB Output is correct
15 Correct 65 ms 251516 KB Output is correct
16 Correct 604 ms 261748 KB Output is correct
17 Correct 259 ms 261776 KB Output is correct
18 Correct 253 ms 261612 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 250712 KB Output is correct
2 Correct 36 ms 251104 KB Output is correct
3 Correct 36 ms 250708 KB Output is correct
4 Correct 41 ms 251096 KB Output is correct
5 Correct 39 ms 250960 KB Output is correct
6 Correct 39 ms 250964 KB Output is correct
7 Correct 35 ms 250708 KB Output is correct
8 Correct 134 ms 258636 KB Output is correct
9 Correct 176 ms 254356 KB Output is correct
10 Correct 417 ms 261304 KB Output is correct
11 Correct 258 ms 261964 KB Output is correct
12 Correct 245 ms 261968 KB Output is correct
13 Correct 35 ms 250704 KB Output is correct
14 Correct 140 ms 258720 KB Output is correct
15 Correct 65 ms 251472 KB Output is correct
16 Correct 654 ms 261592 KB Output is correct
17 Correct 256 ms 261676 KB Output is correct
18 Correct 257 ms 261760 KB Output is correct
19 Runtime error 519 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -