제출 #1006118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1006118		c2zi6	벽 (IOI14_wall)	C++14	100 / 100	502 ms	100540 KiB

wall

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "wall.h"

PII perform(PII a, PII b) {
    PII ret = {max(a.ff, b.ff), min(a.ss, b.ss)};
    if (ret.ff > ret.ss) {
        if (b.ff > a.ss) return {b.ff, b.ff};
        return {b.ss, b.ss};
    }
    return ret;
}
struct SEGTREE {
    int n;
    VPI tree;
    VPI lazy;
    SEGTREE(int sz) {
        n = 1;
        while (n < sz) n *= 2;
        tree = VPI(2*n, {0, +1e9});
        lazy = VPI(2*n, {0, +1e9});
    }
    void push(int N) {
        if (N < n-1) {
            lazy[2*N+1] = perform(lazy[2*N+1], lazy[N]);
            lazy[2*N+2] = perform(lazy[2*N+2], lazy[N]);
        } else {
            tree[N] = perform(tree[N], lazy[N]);
        }
        lazy[N] = {0, +1e9};
    }
    void setmx(int N, int L, int R, int l, int r, int h) {
        push(N);
        if (R < l || L > r) return;
        if (l <= L && R <= r) {
            lazy[N] = {0, h};
            push(N);
            return;
        }
        int M = (L+R)/2;
        setmx(2*N+1, L, M, l, r, h);
        setmx(2*N+2, M+1, R, l, r, h);
    }
    void setmn(int N, int L, int R, int l, int r, int h) {
        push(N);
        if (R < l || L > r) return;
        if (l <= L && R <= r) {
            lazy[N] = {h, +1e9};
            push(N);
            return;
        }
        int M = (L+R)/2;
        setmn(2*N+1, L, M, l, r, h);
        setmn(2*N+2, M+1, R, l, r, h);
    }
    void print(int N, int L, int R) {
        if (N > 2*n-2) return;
        cout << N << "," << L+1 << ".." << R+1 << ": " << lazy[N].ff << ".." << lazy[N].ss << endl;
        int M = (L+R)/2;
        print(2*N+1, L, M);
        print(2*N+2, M+1, R);
    }
    void print() {
        print(0, 0, n-1);
        replr(i, n-1, 2*n-2) {
            cout << tree[i].ff << ".." << tree[i].ss << endl;
        }
    }
    void finish(int N = 0) {
        if (N > 2*n-2) return;
        push(N);
        finish(2*N+1);
        finish(2*N+2);
    }
    VI verj() {
        VI ret;
        replr(i, n-1, 2*n-2) ret.pb(tree[i].ff);
        return ret;
    }
    void setmx(int l, int r, int h) {
        setmx(0, 0, n-1, l, r, h);
    }
    void setmn(int l, int r, int h) {
        setmn(0, 0, n-1, l, r, h);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SEGTREE seg(n);
    for (int i = 0; i < k; i++) {
        int l = left[i];
        int r = right[i];
        int h = height[i];
        /*l--, r--;*/
        if (op[i] == 1) seg.setmn(l, r, h);
        else seg.setmx(l, r, h);
        /*seg.print();*/
        /*cout << "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAa" << endl;*/
    }
    seg.finish();
    VI ans = seg.verj();
    rep(i, n) finalHeight[i] = ans[i];
}

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