Submission #408115

#	Time	Username	Problem	Language	Result	Execution time	Memory
408115		mshandilya	Wall (IOI14_wall)	C++14	0 / 100	244 ms	13900 KiB

wall

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

using namespace std;

void add(std::vector<int>& ST, std::vector<int>& lazy, int update, int rbeg, int rend, int beg, int end, int node) {
	if(rbeg>rend)
		return;
	if(lazy[node-1]!=-1) {
		ST[node-1] = lazy[node-1];
		lazy[2*node-1] = lazy[node-1];
		lazy[2*node] = lazy[node-1]; 
		lazy[node-1] = -1;
	}
	if(rbeg==beg and rend==end) {
		ST[node-1] = max(update, ST[node-1]);
		if(lazy[2*node-1]==-1)
			lazy[2*node-1] = max(update, ST[2*node-1]);
		else
			lazy[2*node-1] = max(update, lazy[2*node-1]);
		if(lazy[2*node]==-1)
			lazy[2*node] = max(update, ST[2*node]);
		else
			lazy[2*node] = max(update, lazy[2*node]);
		return;
	}
	int mid = (beg+end)/2;
	add(ST, lazy, update, rbeg, min(mid, rend), beg, mid, 2*node);
	add(ST, lazy, update, max(rbeg, mid+1), rend, mid+1, end, 2*node+1);
	return;
}

void remov(std::vector<int>& ST, std::vector<int>& lazy, int update, int rbeg, int rend, int beg, int end, int node) {
	if(rbeg>rend)
		return;
	if(lazy[node-1]!=-1) {
		ST[node-1] = lazy[node-1];
		lazy[2*node-1] = lazy[node-1];
		lazy[2*node] = lazy[node-1];
		lazy[node-1] = -1;
	}
	if(rbeg==beg and rend==end) {
		ST[node-1] = min(update, ST[node-1]);
		if(lazy[2*node-1]==-1)
			lazy[2*node-1] = min(update, ST[2*node-1]);
		else
			lazy[2*node-1] = min(update, lazy[2*node-1]);
		if(lazy[2*node]==-1)
			lazy[2*node] = min(update, ST[2*node]);
		else
			lazy[2*node] = min(update, lazy[2*node]);
		return;
	}
	int mid = (beg+end)/2;
	remov(ST, lazy, update, rbeg, min(mid, rend), beg, mid, 2*node);
	remov(ST, lazy, update, max(rbeg, mid+1), rend, mid+1, end, 2*node+1);
	return;
}

int retrieve(std::vector<int>& ST, std::vector<int>& lazy, int find, int beg, int end, int node) {
	if(lazy[node-1]!=-1) {
		ST[node-1] = lazy[node-1];
		lazy[2*node-1] = lazy[node-1];
		lazy[2*node] = lazy[node-1];
		lazy[node-1] = -1;
	}
	if(beg==end)
		return ST[node-1];
	int mid = (beg+end)/2;
	if(find<=mid)
		return retrieve(ST, lazy, find, beg, mid, 2*node);
	else
		return retrieve(ST, lazy, find, mid+1, end, 2*node+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	int st_size = 1;
	while(st_size<n)
		st_size<<=1;
	std::vector<int> ST(2*st_size-1, 0), lazy(2*st_size-1, -1);
	for (int i = 0; i<k; ++i) {
		if(op[i]==1)
			add(ST, lazy, height[i], left[i], right[i], 0, st_size-1, 1);
		else
			remov(ST, lazy, height[i], left[i], right[i], 0, st_size-1, 1);	
	}
	for(int i = 0; i<n; i++)
		finalHeight[i] = retrieve(ST, lazy, i, 0, st_size-1, 1);
	return;
}

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