Submission #52133

#	Time	Username	Problem	Language	Result	Execution time	Memory
52133		shoemakerjo	Wall (IOI14_wall)	C++14	0 / 100	1153 ms	102860 KiB

wall

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

using namespace std;
#define maxn 2000010
#define maxk 500010
int seg[maxn*4];
int lazy[maxn*4];
int lazyt[maxn*4];

int N, K;

void delaze(int ss, int se, int si) {
	if (lazy[si] == -1) {
		return;
	}
	if  (lazyt[si] == 1) { //these are maxes
		seg[si] = max(seg[si], lazy[si]);
	}
	else {
		seg[si] = min(seg[si], lazy[si]);
	}
	if (ss != se) {
		for (int d = 1; d <= 2; ++d) {
			if (lazyt[si*2+d] == -1) {
				lazy[si*2+d] = lazy[si];
				lazyt[si*2+d] = lazyt[si];
			}
			else {
				if (lazyt[si] == 1) {
					if (lazyt[si*2+d] == 1) {
						lazy[si*2+d] = max(lazy[si*2+d], lazy[si]);
					}
					else {
						//there is a min there, and then we take the max with the new thing
						//basically if the max is below the min we do nothing, otherwise we do the max only
						if (lazy[si] >= lazy[si*2+d]) {
							lazy[si*2+d] = lazy[si];
							lazyt[si*2+d] = lazyt[si];
						}
					}
				}
				else {
					if (lazyt[si*2+d] == 2) {
						lazy[si*2+d] = min(lazy[si*2+d], lazy[si]);
					}
					else {
						//there is a max there, and then we take the min
						if (lazy[si] <= lazy[si*2+d]) {
							lazy[si*2+d] = lazy[si];
							lazyt[si*2+d] = lazyt[si];
						}
					}
				}
			}
		}
		
		
	}

	lazy[si] = lazyt[si] = -1;

}


void up(int us, int ue, int type, int h, 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) {
		lazy[si] = h;
		lazyt[si] = type;
		delaze(ss, se, si);
		return;
	}
	int mid = (ss+se)/2;
	up(us, ue, type, h, ss, mid, si*2+1);
	up(us, ue, type, h, mid+1, se, si*2+2);

}

void update(int us, int ue, int type, int h) {
	up(us, ue, type, h, 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(lazy, lazy+maxn*4, -1);
	fill(lazyt, lazyt+maxn*4, -1);
	N = n;
	K = k;

	//do the queries
	for (int i = 0; i < k; i++) {
		update(left[i], right[i], op[i], height[i]);
	}
	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