Submission #1267461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267461		cmiuc	벽 (IOI14_wall)	C++20	100 / 100	769 ms	57800 KiB

wall

#include <iostream>
#include "wall.h"

using namespace std;
const int Nn = (1<<21) + 1;
int Mx[Nn<<1], Mn[Nn<<1], inf = 1e9;

void update(int cur, int tp, int h){
	if (tp == 1){
		Mx[cur] = max(Mx[cur], h);
		Mn[cur] = max(Mn[cur], h);
	}
	else{
		Mn[cur] = min(Mn[cur], h);
		Mx[cur] = min(Mx[cur], h);
	}
}

void update(int tp, int l, int r, int h, int cur = 1, int st = 1, int en = Nn){
	if (l >= en or r <= st)
		return;
	if (l <= st and r >= en){
		update(cur, tp, h);
		return;
	}

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	
	update(lc, 1, Mx[cur]);
	update(lc, 2, Mn[cur]);
	update(rc, 1, Mx[cur]);
	update(rc, 2, Mn[cur]);

	update(tp, l, r, h, lc, st, mid);
	update(tp, l, r, h, rc, mid, en);
	Mx[cur] = min(Mx[lc], Mx[rc]);
	Mn[cur] = max(Mn[lc], Mn[rc]);

}

int get(int i, int cur = 1, int st = 1, int en = Nn){
	if (i >= en or i < st)
		return 0;
	if (en - st == 1)
		return max(0, Mx[cur]);
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	
	update(lc, 1, Mx[cur]);
	update(lc, 2, Mn[cur]);
	update(rc, 1, Mx[cur]);
	update(rc, 2, Mn[cur]);
	return get(i, lc, st, mid) + get(i, rc, mid, en);
}

void buildWall(int n, int k, int op[], int lft[], int rgt[], int ht[], int ans[]){
	for (int i=0;i<k;i++)
		update(op[i], lft[i] + 1, rgt[i] + 2, ht[i]);
	
	for (int i=1;i<=n;i++)
		ans[i-1] = get(i);
}

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