제출 #779128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779128		NothingXD	벽 (IOI14_wall)	C++17	100 / 100	730 ms	77356 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef complex<double> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e6 + 10;
const int inf = 1e9;

int n, k, ans[maxn];
pii seg[maxn << 2];

void shift(int v, int l, int r);

void change(int v, int l, int r, int ql, int qr, pii val){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		if (val.F > seg[v].S) seg[v].S = val.F;
		else if (val.S < seg[v].F) seg[v].F = val.S;
		seg[v].F = max(seg[v].F, val.F);
		seg[v].S = min(seg[v].S, val.S);
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	change(v << 1, l, mid, ql, qr, val);
	change(v << 1 | 1, mid, r, ql, qr, val);
	seg[v].F = min(seg[v << 1].F, seg[v << 1 | 1].F);
	seg[v].S = max(seg[v << 1].S, seg[v << 1 | 1].S);
}

void solve(int v, int l, int r){
	if (l + 1 == r){
		ans[l] = seg[v].F;
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	solve(v << 1, l, mid);
	solve(v << 1 | 1, mid, r);
}

void shift(int v, int l, int r){
	int mid = (l + r) >> 1;
	change(v << 1, l, mid, l, mid, seg[v]);
	change(v << 1 | 1, mid, r, mid, r, seg[v]);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < k; i++){
		right[i]++;
		if (op[i] == 1){
			change(1, 0, n, left[i], right[i], MP(height[i], inf));
		}
		else{
			change(1, 0, n, left[i], right[i], MP(-inf, height[i]));
		}
	}
	solve(1, 0, n);
	for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
	return;
}

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