Submission #425312

#	Time	Username	Problem	Language	Result	Execution time	Memory
425312		bipartite_matching	Wall (IOI14_wall)	C++14	0 / 100	625 ms	87348 KiB

wall

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

#define forint(i, N) for (int i = 0; i < (N); i++)

using namespace std;

vector<int> mintree(10000000, 0);
vector<int> maxtree(10000000, 0);

void updatemin(int node, int a, int b, int x, int y, int k) {
	if (a <= x && y <= b) {
		if (mintree[node] >= k) return;
		mintree[node] = k;
		if (maxtree[node] < mintree[node]) {
			maxtree[node] = k;
		}
		if (mintree[node * 2 + 1] < mintree[node]) {
			mintree[node * 2 + 1] = mintree[node];
			if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
				maxtree[node * 2 + 1] = mintree[node * 2 + 1];
			}
		}
		if (mintree[node * 2 + 2] < mintree[node]){
			mintree[node * 2 + 2] = mintree[node];
			if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
				maxtree[node * 2 + 2] = mintree[node * 2 + 2];
			}
		}
		return;
	}

	if (mintree[node * 2 + 1] < mintree[node]) {
		mintree[node * 2 + 1] = mintree[node];
		if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
			maxtree[node * 2 + 1] = mintree[node * 2 + 1];
		}
	}
	if (mintree[node * 2 + 2] < mintree[node]){
		mintree[node * 2 + 2] = mintree[node];
		if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
			maxtree[node * 2 + 2] = mintree[node * 2 + 2];
		}
	}
	if ((x + y) / 2 >= a) {
		updatemin(node * 2 + 1, a, b, x, (x + y) / 2, k);
	}
	if ((x + y) / 2 + 1 <= b) {
		updatemin(node * 2 + 2, a, b, (x + y) / 2 + 1, y, k);
	}

	maxtree[node] = max(maxtree[node * 2 + 1], maxtree[node * 2 + 2]);
	mintree[node] = min(mintree[node * 2 + 1], mintree[node * 2 + 2]);
	if (maxtree[node] < mintree[node]) {
		maxtree[node] = mintree[node];
	}
}

void updatemax(int node, int a, int b, int x, int y, int k) {
	if (a <= x && y <= b) {
		if (maxtree[node] <= k) return;
		maxtree[node] = k;
		if (maxtree[node] < mintree[node]) {
			mintree[node] = k;
		}
		if (maxtree[node * 2 + 1] > maxtree[node]) {
			maxtree[node * 2 + 1] = maxtree[node];
			if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
				mintree[node * 2 + 1] = maxtree[node * 2 + 1];
			}
		}
		if (maxtree[node * 2 + 2] > maxtree[node]) {
			maxtree[node * 2 + 2] = maxtree[node];
			if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
				mintree[node * 2 + 2] = maxtree[node * 2 + 2];
			}
		}
		return;
	}
	if (maxtree[node * 2 + 1] > maxtree[node]) {
		maxtree[node * 2 + 1] = maxtree[node];
		if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) {
			mintree[node * 2 + 1] = maxtree[node * 2 + 1];
		}
	}
	if (maxtree[node * 2 + 2] > maxtree[node]) {
		maxtree[node * 2 + 2] = maxtree[node];
		if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) {
			mintree[node * 2 + 2] = maxtree[node * 2 + 2];
		}
	}

	if ((x + y) / 2 >= a) {
		updatemax(node * 2 + 1, a, b, x, (x + y) / 2, k);
	}
	if ((x + y) / 2 + 1 <= b) {
		updatemax(node * 2 + 2, a, b, (x + y) / 2 + 1, y, k);
	}

	maxtree[node] = max(maxtree[node * 2 + 1], maxtree[node * 2 + 2]);
	mintree[node] = min(mintree[node * 2 + 1], mintree[node * 2 + 2]);
	if (maxtree[node] < mintree[node]) {
		mintree[node] = maxtree[node];
	}
}

int pos = 0;
vector<int> heightfinal;

void search(int node, int x, int y, int target) {
	//cerr << target << " ---- " << mintree[node] << " ---- " << maxtree[node] << "  - - " << x << "--" << y << endl;
	if (mintree[node] == maxtree[node]) {
		for (int i = target; i <= y; i++) {
			heightfinal[i] = mintree[node];
		}
		pos = y + 1;
		return;
	}

	if (mintree[node * 2 + 1] < mintree[node]) {
		mintree[node * 2 + 1] = mintree[node];
		if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) maxtree[node * 2 + 1] = mintree[node * 2 + 1];
	}
	if (mintree[node * 2 + 2] < mintree[node]) {
		mintree[node * 2 + 2] = mintree[node];
		if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) maxtree[node * 2 + 2] = mintree[node * 2 + 2];
	}
	if (maxtree[node * 2 + 1] > maxtree[node]) {
		maxtree[node * 2 + 1] = maxtree[node];
		if (maxtree[node * 2 + 1] < mintree[node * 2 + 1]) mintree[node * 2 + 1] = maxtree[node * 2 + 1];
	}
	if (maxtree[node * 2 + 2] > maxtree[node]) {
		maxtree[node * 2 + 2] = maxtree[node];
		if (maxtree[node * 2 + 2] < mintree[node * 2 + 2]) mintree[node * 2 + 2] = maxtree[node * 2 + 2];
	}

	if ((x + y) / 2 >= target) {
		search(node * 2 + 1, x, (x + y) / 2, target);
	}
	else {
		search(node * 2 + 2, (x + y) / 2 + 1, y, target);
	}
	
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	forint(i, k) {
		if (op[i] == 1) {
			updatemin(0, left[i], right[i], 0, n - 1, height[i]);
		}
		else {
			updatemax(0, left[i], right[i], 0, n - 1, height[i]);
		}
	}
	

	heightfinal.resize(n);
	while (pos < n) {
		//cerr << "hello" << endl;
		search(0, 0, n - 1, pos);
	}

	forint(i, n) {
		finalHeight[i] = heightfinal[i];
	}
}

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