Submission #73879

#	Time	Username	Problem	Language	Result	Execution time	Memory
73879		Hoget157	Wall (IOI14_wall)	C++14	100 / 100	1069 ms	153096 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define INF 1e+9
using namespace std;

typedef pair<int,int> P;

P dat[1050000];
int seg = 1;

P add(P p1,P p2){
	int a = p1.first,b = p1.second,c = p2.first,d = p2.second;
	return P(min(a,max(c,d)),min(max(b,d),max(c,d)));
}

int f(int x,P p){
	return max(min(x,p.first),p.second);
}

void update(int i,P x){
	i += seg - 1;
	dat[i] = x;
	while(i){
		i = (i - 1) / 2;
		dat[i] = add(dat[i * 2 + 1],dat[i * 2 + 2]);
	}
}

void buildWall(int n, int k, int op[], int l[], int r[], int height[], int finalHeight[]){
	while(seg < k) seg *= 2;
	for(int i = 0;i < seg * 2 - 1;i++) dat[i] = P(INF,0);
	vector<int> on[2000010],off[2000010];
	for(int i = 0;i < k;i++){
		on[l[i]].push_back(i);
		off[r[i]].push_back(i);
	}
	for(int i = 0;i < n;i++){
		for(int v : on[i]){
			if(op[v] == 1) update(v,P(INF,height[v]));
			else update(v,P(height[v],0));
		}
		finalHeight[i] = f(0,dat[0]);
		for(int v : off[i]) update(v,P(INF,0));
	}
}

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