oj.uz

답안 #894028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
894028 2023-12-27T20:18:54 Z raul2008487 벽 (IOI14_wall) C++17
0 / 100
 116 ms 8184 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;
vector<array<ll, 2>> st;
const ll dh = 100000;
ll res[2000005];
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 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(tl == tr){
            if(type == 1){
                st[v][0] = max(st[v][0], val);
                st[v][1] = st[v][0];
            }
            else{
                st[v][0] = min(st[v][0], val);
                st[v][1] = st[v][0];
            }
            return ;
        }
        if(type == 1){
            st[v] = {val, dh};
        }
        else{
            st[v] = {0, val};
        }
        //push(v, tl, tr);
        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){
        return ;
    }
    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, sz, z = 0;
    sz = 1;
    while(sz < n){
        sz *= 2;
    }
    st.assign(sz*2, {-1, 0});
    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++){
        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:73:11: warning: unused variable 'j' [-Wunused-variable]
   73 |     ll i, j, sz, z = 0;
      |           ^

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 109 ms 8184 KB Output is correct
3 Incorrect 116 ms 4928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -