Submission #939278

#	Time	Username	Problem	Language	Result	Execution time	Memory
939278		a_l_i_r_e_z_a	Wall (IOI14_wall)	C++17	100 / 100	604 ms	107432 KiB

wall

// In the name of God
// Hope is last to die
 
#include <bits/stdc++.h>
using namespace std;
 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
 
const int maxn = 2e6 + 5;
const int inf = 1e5;
struct D{
    int mn, mx;
    D(){
        mn = 0;
        mx = inf;
    }
} node[maxn * 4];
int n, k, ans[maxn];

void change(int id, D d){
    if(d.mn >= node[id].mx) node[id].mn = node[id].mx = d.mn;
    else if(d.mx <= node[id].mn) node[id].mn = node[id].mx = d.mx;
    else{
        smax(node[id].mn, d.mn);
        smin(node[id].mx, d.mx);
    }
}

void relax(int id){
    change(id * 2, node[id]);
    change(id * 2 + 1, node[id]);
    node[id].mn = 0;
    node[id].mx = inf;
}

void upd(int s, int e, int ty, int h, int l = 0, int r = n, int id = 1){
    if(s <= l && r <= e){
        if(ty == 1){
            if(h >= node[id].mx) node[id].mn = node[id].mx = h;
            else smax(node[id].mn, h);
        }
        else{
            if(h <= node[id].mn) node[id].mn = node[id].mx = h;
            else smin(node[id].mx, h);
        }
        return;
    }
    if(e <= l || r <= s) return;
    relax(id);
    int mid = (l + r) / 2;
    upd(s, e, ty, h, l, mid, id * 2);
    upd(s, e, ty, h, mid, r, id * 2 + 1);
}

void get(int l = 0, int r = n, int id = 1){
    if(l == r - 1){
        ans[l] = node[id].mn;
        return;
    }
    relax(id);
    int mid = (l + r) / 2;
    get(l, mid, id * 2);
    get(mid, r, id * 2 + 1);
}

// int32_t main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     cin >> n >> k;
//     while(k--){
//         int l, r, ty, h; cin >> ty >> l >> r >> h;
//         r++;
//         upd(l, r, ty, h);
//     }
//     get();
//     for(int i = 0; i < n; i++) cout << ans[i] << ' ';

//     return 0;
// }


void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N;
    k = K;
    for(int i = 0; i < k; i++) upd(left[i], right[i] + 1, op[i], height[i]);
    get();
    for(int i = 0; i < n; i++) finalHeight[i] = ans[i];
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39