Submission #1173699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173699		fabijan_cikac	Wall (IOI14_wall)	C++20	100 / 100	344 ms	152132 KiB

wall

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

using namespace std;

#define pb push_back
#define pp pair<int, int>
#define F first
#define S second
#define MP make_pair

const int BIT = 19;
const int N = 2 * 1e6 + 100;
const int K = (1 << BIT);
const int INF = 2 * 1e9;

vector<int> sweep[2][N];
pp t[2 * K];

pp merge(pp a, pp b){
	a.F = min(a.F, b.F);
	a.F = max(a.F, b.S);
	a.S = min(a.S, b.F);
	a.S = max(a.S, b.S);
	return a;
}

void upd(int x, pp p){
	x += K; t[x] = p;
	while (x > 1){
		x /= 2; t[x] = merge(t[2 * x], t[2 * x + 1]);
	}
}

//void buildWall(int n, int k, vector<int> op, vector<int> left, vector<int> right, vector<int> height, vector<int> finalHeight){
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

	for (int i = 1; i < 2 * K; ++i)
		t[i] = MP(INF, -INF);

	for (int i = 0; i < k; ++i){
		sweep[0][left[i]].pb(i);
		sweep[1][right[i]].pb(i);
	}
	
	for (int i = 0; i < n; ++i){
		for (int x: sweep[0][i])
			upd(x, op[x] == 1 ? MP(INF, height[x]) : MP(height[x], -INF));
			
		finalHeight[i] = merge(MP(0, 0), t[1]).F;
			
		for (int x: sweep[1][i]) upd(x, MP(INF, -INF));
	}
	
	/*for (int i = 0; i < n; ++i)
		cout << finalHeight[i] << ' ';*/
}

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