Submission #282483

#	Time	Username	Problem	Language	Result	Execution time	Memory
282483		amoo_safar	Wall (IOI14_wall)	C++17	100 / 100	846 ms	71676 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 2097152;
const int Inf = 100000;

int sL[N << 1], sR[N << 1];

void Apply(int id, int lq, int rq){
	sL[id] = max(min(sL[id], rq), lq);
	sR[id] = max(min(sR[id], rq), lq);
}
void Shift(int id){
	Apply(id << 1, sL[id], sR[id]);
	Apply(id << 1 | 1, sL[id], sR[id]);
	sL[id] = 0;
	sR[id] = Inf;
}
void Query(int id, int l, int r, int lq, int rq, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		Apply(id, lq, rq);
		return ;
	}
	Shift(id);
	int mid = (L + R) >> 1;
	Query(id << 1, l, r, lq, rq, L, mid);
	Query(id << 1 | 1, l, r, lq, rq, mid, R);
}
int ans[N];
void DFS(int id, int L, int R){
	if(L + 1 == R){
		//cerr << "# " << L << " ! " << sL[id] << ' ' << sR[id] << '\n';
		ans[L] = sL[id];
		return ;
	}
	int mid = (L + R) >> 1;
	Shift(id);
	DFS(id << 1, L, mid);
	DFS(id << 1 | 1, mid, R); 
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	fill(sR, sR + N*2, Inf);
	for(int i = 0; i < k; i++){
		Query(1, left[i], right[i] + 1, op[i] == 1 ? height[i] : 0, op[i] == 2 ? height[i] : Inf, 0, n);
	}
	DFS(1, 0, n);
	for(int i = 0; i < n; i++) finalHeight[i] = ans[i];
	return;
}

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