Submission #1040792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040792		lovrot	벽 (IOI14_wall)	C++17	100 / 100	358 ms	69500 KiB

wall

#include "wall.h"
#include <algorithm>
#include <set>
#include <vector>
#include <cstdio>

#define PB push_back
#define debug(...) //fprintf(stderr, __VA_ARGS__)

using namespace std;

const int LOG = 21;
const int N = 1 << LOG;
const int OO = 0x7FFFFFFF;

struct node {
	int a, b;
	node() : a(0), b(OO) {}
	node(int a, int b) : a(a), b(b) {}
};

node t[2 * N];

void merge(int &a, int &b, int l, int r) { 
	a = min(r, max(l, a));
	b = max(l, min(r, b));
}

void propagate(int u) { 
	merge(t[2 * u].a, t[2 * u].b, t[u].a, t[u].b);
	merge(t[2 * u + 1].a, t[2 * u + 1].b, t[u].a, t[u].b);
	t[u].a = 0;
	t[u].b = OO;
}

void update(int l, int r, int a, int b, int u = 1, int lo = 0, int hi = N) { 
	if(r <= lo || hi <= l) { 
		return;
	}
	if(l <= lo && hi <= r) { 
		merge(t[u].a, t[u].b, a, b);
		return;
	}
	int mi = (lo + hi) / 2;
	propagate(u);
	update(l, r, a, b, 2 * u, lo, mi);
	update(l, r, a, b, 2 * u + 1, mi, hi);
}

void query(int u = 1, int lo = 0, int hi = N) { 
	if(u >= N) { return; }
	int mi = (lo + hi) / 2;
	propagate(u);
	query(2 * u, lo, mi);
	query(2 * u + 1, mi, hi);
}
			
void buildWall(int n, int k, int op[], int lft[], int rgt[], int hgt[], int fnl[]){
	for(int i = 0; i < k; ++i) { 
		int a, b;
		if(op[i] == 1) {
			a = hgt[i];
			b = OO;
		} else {
			a = 0;
			b = hgt[i];
		}
		update(lft[i], rgt[i] + 1, a, b);
	}

	query();

	for(int i = 0; i < n; ++i) { 
		fnl[i] = t[N + i].a;
		debug("%d %d\n", i, fnl[i]);
	}
	return;
}

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