Submission #1166390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166390		fabijan_cikac	Wall (IOI14_wall)	C++20	0 / 100	0 ms	328 KiB

wall

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

using namespace std;

#define ll long long
#define pb push_back
#define pp pair<int, int>
#define F first
#define S second
#define pnode Node*

const int BITN = 17;
const int BITH = 17;
const int MAXN = (1 << BITN);
const int MAXH = (1 << BITH);
const int SZ = 1e6;

struct Node{
	int l1, r1, l2, r2;
	bool val; int prop;
	Node *A, *B, *C, *D;
	
	Node(int L1, int R1, int L2, int R2) : l1(L1), r1(R1), l2(L2), r2(R2), val(0), prop(-1), A(NULL), B(NULL), C(NULL), D(NULL) {}
};

vector<Node> arr;

int cnt = 0;
pnode new_node(int l1, int r1, int l2, int r2){
	arr.pb(Node(l1, r1, l2, r2));
	return &arr.back();
}

void propagate(pnode x){
	if (x->prop == -1) return;
	
	x->val = x->prop;
	if (x->A) x->A->prop = x->prop;
	if (x->B) x->B->prop = x->prop;
	if (x->C) x->C->prop = x->prop;
	if (x->D) x->D->prop = x->prop;
	
	x->prop = -1; return;
}

void upd(pnode x, int l1, int r1, int l2, int r2, bool V){
	if (x == NULL) return;
	
	//cout << "!!! " << x->l1 << ' ' << x->r1 << ' ' << x->l2 << ' ' << x->r2 << " : " << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << " ::: " << V << endl;
	int mid1 = (x->l1 + x->r1) / 2;
	int mid2 = (x->l2 + x->r2) / 2;
	
	if (!x->A && mid2 < x->r2) x->A = new_node(x->l1, mid1, mid2 + 1, x->r2);
	if (!x->B && mid1 < x->r1 && mid2 < x->r2) x->B = new_node(mid1 + 1, x->r1, mid2 + 1, x->r2);
	if (!x->C && mid1 < x->r1) x->C = new_node(mid1 + 1, x->r1, x->l2, mid2);
	if (!x->D) x->D = new_node(x->l1, mid1, x->l2, mid2);
	
	//cout << "ok" << endl;
	
	propagate(x);
	if (x->r1 < l1 || x->l1 > r1 || x->r2 < l2 || x->l2 > r2) return;
	if (x->l1 >= l1 && x->r1 <= r1 && x->l2 >= l2 && x->r2 <= r2){
		x->prop = V, propagate(x);
		//cout << "UPD " << x->l1 << ' ' << x->r1 << ' ' << x->l2 << ' ' << x->r2 << endl;
		return;
	}
	
	//cout << "rasiri" << endl;
	
	upd(x->A, l1, r1, l2, r2, V);
	upd(x->B, l1, r1, l2, r2, V);
	upd(x->C, l1, r1, l2, r2, V);
	upd(x->D, l1, r1, l2, r2, V);
	x->val = (x->A ? x->A->val : 0) | (x->B ? x->B->val : 0) | (x->C ? x->C->val : 0) | (x->D ? x->D->val : 0);
	return;
}

bool query(pnode x, int l1, int r1, int l2, int r2){
	if (x == NULL) return 0;
	int mid1 = (x->l1 + x->r1) / 2;
	int mid2 = (x->l2 + x->r2) / 2;
	
	if (!x->A && mid2 < x->r2) x->A = new_node(x->l1, mid1, mid2 + 1, x->r2);
	if (!x->B && mid1 < x->r1 && mid2 < x->r2) x->B = new_node(mid1 + 1, x->r1, mid2 + 1, x->r2);
	if (!x->C && mid1 < x->r1) x->C = new_node(mid1 + 1, x->r1, x->l2, mid2);
	if (!x->D) x->D = new_node(x->l1, mid1, x->l2, mid2);
	
	propagate(x);
	if (x->r1 < l1 || x->l1 > r1 || x->r2 < l2 || x->l2 > r2) return 0;
	if (x->l1 >= l1 && x->r1 <= r1 && x->l2 >= l2 && x->r2 <= r2) return x->val;
	
	return query(x->A, l1, r1, l2, r2) | query(x->B, l1, r1, l2, r2) | query(x->C, l1, r1, l2, r2) | query(x->D, l1, r1, l2, r2);
}

/*int n = 10, k = 6;
int op[6] = {1, 2, 2, 1, 1, 2};
int Left[6] = {1, 4, 3, 0, 2, 6};
int Right[6] = {8, 9, 6, 5, 2, 7};
int height[6] = {4, 1, 5, 3, 5, 0};*/

//void buildWall(){
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	pnode root = new_node(1, MAXN, 1, MAXH);
	
	for (int i = 0; i < k; ++i)
		--op[i], ++left[i], ++right[i];
	for (int i = 0; i < k; ++i){
		if (!op[i]) upd(root, left[i], right[i], 1, height[i], 1);
		else upd(root, left[i], right[i], height[i] + 1, MAXH, 0);
	}
	
	for (int i = 1; i <= n; ++i){
		int h = MAXH;
		for (int j = BITH - 1; j >= 0; --j)
			if (h > (1 << j) && !query(root, i, i, h - (1 << j), MAXH)) h -= (1 << j);
		//cout << h - 1 << ' ';
		finalHeight[i - 1] = h - 1;
	}
	
	return;
}

/*int main(){
	buildWall();
	//buildWall(10, 6, {1, 2, 2, 1, 1, 2}, {1, 4, 3, 0, 2, 6}, {8, 9, 6, 5, 2, 7}, {4, 1, 5, 3, 5, 0}, {});
	return 0;
}*/

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