Submission #485436

#	Time	Username	Problem	Language	Result	Execution time	Memory
485436		penguinhacker	Wall (IOI14_wall)	C++14	100 / 100	621 ms	69732 KiB

wall

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

#define ll long long
#define ar array

const int mxN=2e6;
const ar<int, 2> ID={0, mxN};
int n;
ar<int, 2> st[1<<22];

ar<int, 2> app(ar<int, 2> a, ar<int, 2> b) {
	a[0]=max(a[0], b[0]);
	a[1]=max(a[1], b[0]);
	a[0]=min(a[0], b[1]);
	a[1]=min(a[1], b[1]);
	return a;
}

void psh(int u) {
	if (st[u]!=ID) {
		st[2*u]=app(st[2*u], st[u]);
		st[2*u+1]=app(st[2*u+1], st[u]);
		st[u]=ID;
	}
}

void upd(int ql, int qr, ar<int, 2> x, int u=1, int l=0, int r=n-1) {
	if (ql<=l&&r<=qr) {
		st[u]=app(st[u], x);
		return;
	}
	psh(u);
	int mid=(l+r)/2;
	if (ql<=mid)
		upd(ql, qr, x, 2*u, l, mid);
	if (qr>mid)
		upd(ql, qr, x, 2*u+1, mid+1, r);
}

void solve(int ans[], int u=1, int l=0, int r=n-1) {
	if (l==r) {
		assert(st[u][0]==st[u][1]);
		ans[l]=st[u][0];
		return;
	}
	int mid=(l+r)/2;
	psh(u);
	solve(ans, 2*u, l, mid);
	solve(ans, 2*u+1, mid+1, r);
}

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) {
		if (op[i]==1)
			upd(left[i], right[i], {height[i], mxN});
		else
			upd(left[i], right[i], {0, height[i]});
	}
	solve(finalHeight);
}

/*int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _n=10, _k=6;
	int _op[6]={1, 2, 2, 1, 1, 2};
	int _left[6]={1, 4, 3, 0, 2, 6};
	int _right[6]={8, 9, 6, 5, 2, 7};
	int _height[6]={4, 1, 5, 3, 5, 0};
	int _ans[10];
	buildWall(_n, _k, _op, _left, _right, _height, _ans);
	for (int i=0; i<10; ++i)
		cout << _ans[i] << " ";
	return 0;
}*/

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