제출 #1196358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196358		AMel0n	Wall (IOI14_wall)	C++20	0 / 100	77 ms	8008 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FOR(i,N) for(int i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first 
#define S second

const int INF = 1e9+7;

int N;
vector<int> tree, lazy;

void pushdown(int type, int tl, int tr, int i) {
    if (lazy[i] != -INF) {
        if (tree[i] < lazy[i] && type == 1) tree[i] = lazy[i]; // add
        if (tree[i] > lazy[i] && type == 2) tree[i] = lazy[i]; // remove
        if (tl != tr) {
            lazy[i*2] = lazy[i];
            lazy[i*2+1] = lazy[i];
        }
        lazy[i] = -INF;
    }
}

void update(int type, int v, int l, int r, int tl = 0, int tr = N-1, int i = 1) {
    pushdown(type, tl, tr, i);
    if (l > r) return;
    if (tl == l && tr == r) {
        lazy[i] = v;
        pushdown(type, tl, tr, i);
        return;
    }
    int tm = (tl + tr) / 2;
    update(v, l, min(r, tm), tl, tm, i * 2);
    update(v, max(l, tm + 1), r, tm + 1, tr, i * 2 + 1);
    tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}

int query(int l, int r, int tl = 0, int tr = N-1, int i = 1) {
    pushdown(-1, tl, tr, i);
    if (l > r) return -INF;
    if (tl == l && tr == r) return tree[i];
    int tm = (tl + tr) / 2;
    return max(query(l, min(r, tm), tl, tm, i * 2), query(max(l, tm + 1), r, tm + 1, tr, i * 2 + 1));
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    N = n;
    tree.resize(4*N);
    lazy.resize(4*N, -INF);
    FOR(i,k) {
        update(op[i], height[i], left[i], right[i]);
    }
    FOR(i,n) {
        finalHeight[i] = query(i,i);
    }
}

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