Submission #545507

#	Time	Username	Problem	Language	Result	Execution time	Memory
545507		benson1029	Wall (IOI14_wall)	C++14	100 / 100	719 ms	114968 KiB

wall

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

int seg1[8000005], seg2[8000005]; // min, max
int inf = 1e9;
int mn[2000005], mx[2000005];

void push(int x, int l, int r) {
	if(l==r) return;
	
	seg1[x*2] = min(seg1[x*2], seg1[x]);
	seg2[x*2] = min(seg2[x*2], seg1[x]);
	seg1[x*2] = max(seg1[x*2], seg2[x]);
	seg2[x*2] = max(seg2[x*2], seg2[x]);
	
	seg1[x*2+1] = min(seg1[x*2+1], seg1[x]);
	seg2[x*2+1] = min(seg2[x*2+1], seg1[x]);
	seg1[x*2+1] = max(seg1[x*2+1], seg2[x]);
	seg2[x*2+1] = max(seg2[x*2+1], seg2[x]);
	
	seg1[x] = inf; seg2[x] = -inf;
}

void upd(int x, int l, int r, int ll, int rr, int tp, int val) {
	if(l > rr || r < ll) return;
	push(x, l, r);
	if(ll <= l && r <= rr) {
		if(tp==1) { // max operation
			seg1[x] = max(seg1[x], val);
			seg2[x] = max(seg2[x], val);
		} else {
			seg1[x] = min(seg1[x], val);
			seg2[x] = min(seg2[x], val);
		}
	} else {
		upd(x*2, l, (l+r)/2, ll, rr, tp, val);
		upd(x*2+1, (l+r)/2+1, r, ll, rr, tp, val);
	}
}

void qry(int x, int l, int r) {
	push(x, l, r);
	if(l==r) {
		mn[l] = seg1[x];
		mx[l] = seg2[x];
	} else {
		qry(x*2, l, (l+r)/2);
		qry(x*2+1, (l+r)/2+1, r);
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	memset(seg1, inf, sizeof(seg1));
	memset(seg2, -inf, sizeof(seg2));
	
	for(int i=0; i<k; i++) {
		upd(1, 0, n-1, left[i], right[i], op[i], height[i]);
	}
	qry(1, 0, n-1);
	
	for(int i=0; i<n; i++) {
		finalHeight[i] = max(min(0, mn[i]), mx[i]);
	}
}

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