Submission #385405

#	Time	Username	Problem	Language	Result	Execution time	Memory
385405		alishahali1382	벽 (IOI14_wall)	C++14	100 / 100	787 ms	97772 KiB

wall

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

using namespace std;

typedef pair<int, int> pii;
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}

const int inf=1000000100;
const int MAXN=2000010;

int A[MAXN];
pii seg[MAXN<<2];

pii Merge(pii a, pii b){
	if (a.second<b.first) return {b.first, b.first};
	if (b.second<a.first) return {b.second, b.second};
	return {max(a.first, b.first), min(a.second, b.second)};
}
void shift(int id){
	seg[id<<1]=Merge(seg[id<<1], seg[id]);
	seg[id<<1 | 1]=Merge(seg[id<<1 | 1], seg[id]);
	seg[id]=seg[0];
}
void Put(int id, int tl, int tr, int l, int r, pii p){
	if (r<=tl || tr<=l) return ;
	if (l<=tl && tr<=r){
		seg[id]=Merge(seg[id], p);
		// debugp(seg[id])
		return ;
	}
	shift(id);
	int mid=(tl+tr)>>1;
	Put(id<<1, tl, mid, l, r, p);
	Put(id<<1 | 1, mid, tr, l, r, p);
}
void dfs(int id, int tl, int tr){
	if (tr-tl==1){
		A[tl]=Merge({0, 0}, seg[id]).first;
		return ;
	}
	shift(id);
	int mid=(tl+tr)>>1;
	dfs(id<<1, tl, mid);
	dfs(id<<1 | 1, mid, tr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	fill(seg, seg+MAXN*4, pii(0, inf));
	for (int i=0; i<k; i++){
		int l=left[i], r=right[i]+1, h=height[i];
		if (op[i]==1) Put(1, 0, n, l, r, {h, inf});
		if (op[i]==2) Put(1, 0, n, l, r, {0, h});
	}
	dfs(1, 0, n);
	for (int i=0; i<n; i++) finalHeight[i]=A[i];
	return;
}

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