제출 #1156455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156455		Esgeer	벽 (IOI14_wall)	C++17	0 / 100	820 ms	47788 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2")
#endif
//#define int long long
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vb vector<bool>
#define vvb vector<vb>
#define endl '\n'
#define sp <<' '<<
#define F(i, s, n) for(int i = s; i < (int) n; i++)
#define pb push_back
#define fi first
#define se second

const int N = 1e6+5;
const int inf = 1e7;

struct Update {
    int mn, mx;
};
Update lazy[N*4];
int a[N];

Update merge(Update nw, Update old) {
    Update merged;
    merged.mn = max(old.mn, nw.mn);
    merged.mx = min(old.mx, nw.mx);
    if(merged.mn > merged.mx) {
        if(nw.mn > old.mx) {
            merged.mx = merged.mn;
        } else {
            merged.mn = merged.mx;
        }
    }
    return merged;
}

void push_down(int node, int l, int r) {
    if(lazy[node].mn == 0 && lazy[node].mx == inf) return;
    if(l == r) {
        a[l] = lazy[node].mn;
        return; 
    }
    lazy[node*2+1] = merge(lazy[node], lazy[node*2+1]);
    lazy[node*2+2] = merge(lazy[node], lazy[node*2+2]);
    lazy[node] = {0, inf};
}

void update(int node, int l, int r, int L, int R, int mn, int mx) {
    push_down(node, l, r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        lazy[node] = merge({mn, mx}, lazy[node]);
        return;
    }
    int m = (l + r) >> 1;

    update(node*2+1, l, m, L, R, mn, mx);
    update(node*2+2, m+1, r, L, R, mn, mx);
}

void finalize(int node, int l, int r) {
    push_down(node, l, r);
    if(l != r) {
        int m = (l + r) >> 1;
        finalize(node*2+1, l, m);
        finalize(node*2+2, m+1, r);
    }
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    vi comp;
    F(i, 0, k) {
        comp.pb(left[i]);
        comp.pb(right[i]);
    }
    sort(comp.begin(), comp.end());
    int m = comp.size();
    auto idx = [&comp] (int x) {
        return lower_bound(comp.begin(), comp.end(), x) - comp.begin();
    };
    F(i, 0, m*4) lazy[i] = {0, inf};
    F(i, 0, k) {
        if(op[i] == 1) {
            update(0, 0, m-1, idx(left[i]), idx(right[i]), height[i], inf);
        } else {
            update(0, 0, m-1, idx(left[i]), idx(right[i]), 0, height[i]);
        }
    }
    finalize(0, 0, m-1);
    F(i, 0, n) finalHeight[i] = a[idx(i)];
    return;
}

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