Submission #52389

#	Time	Username	Problem	Language	Result	Execution time	Memory
52389		shoemakerjo	Wall (IOI14_wall)	C++14	0 / 100	1376 ms	196888 KiB

wall

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

using namespace std;
#define maxn 2000010
#define ll long long
#define maxk 500010
const ll inf = 12345678901234567;
ll seg[maxn*4];
ll cmin[maxn*4], cmax[maxn*4];

int N, K;

void delaze(int ss, int se, int si) {
	
	seg[si] = max(seg[si], cmax[si]);
	seg[si] = min(seg[si], cmin[si]);

	if (ss != se) {
		for (int d = 1; d <= 2; d++) {
			int pos = 2*si+d;
			int nmin = cmin[si];
			int nmax = cmax[si];
			if (nmin <= cmax[pos]) {
				cmax[pos] = nmax;
				cmin[pos] = nmin;
				continue;
			}
			if (nmax >= cmin[pos]) {
				cmin[pos] = nmin;
				cmax[pos] = nmax;
				continue;
			}
			if (nmin <= cmin[pos]) {
				cmin[pos] = nmin;
			}
			if (nmax >= cmax[pos]) {
				cmax[pos] = nmax;
			}
		}
	}

	cmin[si] = inf;
	cmax[si] = -1;
}


void up(int us, int ue, ll nmin, ll nmax, int ss, int se, int si) {
	delaze(ss, se, si);
	if (us > ue || ss > se || us > se || ue < ss) return;
	if (us <= ss && se <= ue) {
		cmin[si] = nmin;
		cmax[si] = nmax;
		delaze(ss, se, si);
		return;
	}
	int mid = (ss+se)/2;
	up(us, ue, nmin, nmax, ss, mid, si*2+1);
	up(us, ue, nmin, nmax, mid+1, se, si*2+2);

}

void update(int us, int ue, ll nmin, ll nmax) {
	up(us, ue, nmin, nmax, 0, N-1, 0);
}

int qu(int spot, int ss, int se, int si) {
	delaze(ss, se, si);
	if (ss == se) return seg[si];
	int mid = (ss+se)/2;
	if (spot <= mid) return qu(spot, ss, mid, si*2+1);
	return qu(spot, mid+1, se, si*2+2);
}

int query(int spot) {
	return qu(spot, 0, N-1, 0);
}

void buildWall(int n, int k, int op[], int left[], int right[], 
		int height[], int finalHeight[]){
	fill(seg, seg+maxn*4, 0);
	fill(cmax, cmax+maxn*4, -1);
	fill(cmin, cmin+maxn*4, inf);
	N = n;
	K = k;

	//do the queries
	for (int i = 0; i < k; i++) {
		if (op[i] == 1) {
			//max operation
			update(left[i], right[i], inf, height[i]);
		}
		else {
			//min operation
			update(left[i], right[i], height[i], -1);
		}
	}
	for (int i = 0; i  < n; i++) {
		finalHeight[i] = query(i);
	}
	return;
}

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