제출 #1079375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1079375		vjudge1	Wall (IOI14_wall)	C++17	0 / 100	3 ms	860 KiB

wall

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

const int maxn = 2e6 + 5, inf = 1e9 + 5;
int mi[maxn << 2], mx[maxn << 2], N, res[maxn];
pair<int, int> lazy[maxn << 2];

void pull_inc(int id, int k) {
	mi[id] = max(mi[id], k);
	mx[id] = max(mx[id], k);
	lazy[id].first = max(lazy[id].first, k);
	lazy[id].second = max(lazy[id].second, k);
}

void pull_dec(int id, int k) {
	mi[id] = min(mi[id], k);
	mx[id] = min(mx[id], k);
	lazy[id].first = min(lazy[id].first, k);
	lazy[id].second = min(lazy[id].second, k);
}

void shift(int id){
    if(lazy[id].first != -inf){
        pull_inc(id << 1, lazy[id].first);
        pull_inc(id << 1 | 1, lazy[id].first);
    }
    if(lazy[id].second != inf){
        pull_dec(id << 1, lazy[id].second);
        pull_dec(id << 1 | 1, lazy[id].second);
    }
    lazy[id] = {-inf, inf};
}

void upd(int L, int R, int k, int t, int id = 1, int tl = 0, int tr = N - 1) {
	if (L > tr || R < tl) return;
	if (L <= tl && R >= tr) {
		if (t == 1) pull_inc(id, k);
		else pull_dec(id, k);
	}
	shift(id);
	upd(L, R, k, t, id << 1, tl, (tl + tr) >> 1);
	upd(L, R, k, t, id << 1 | 1, ((tl + tr) >> 1) + 1, tr);
	mi[id] = min(mi[id << 1], mi[id << 1 | 1]);
	mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}

void get(int id = 1, int tl = 0, int tr = N - 1) {
	if (tl == tr) { res[tl] = mi[id]; return; }
	shift(id);
	get(id << 1, tl, (tl + tr) >> 1);
	get(id << 1 | 1, ((tl + tr) >> 1) + 1, tr);
}

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

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