Submission #121574

#	Time	Username	Problem	Language	Result	Execution time	Memory
121574		KieranHorgan	Jousting tournament (IOI12_tournament)	C++17	100 / 100	399 ms	52092 KiB

tournament

// #include "grader.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> AdjList[200005];
int sz[200005];
int curNode = 1;
int N, C, R, *K, *S, *E;
int actualIdxToNode[100005];
int nodeToActualIdx[200005];

struct node {
	node *left, *right;
	int subtreeSize;
	int val;
	node(): left(NULL), right(NULL) {subtreeSize = 1; val = -1;};

};

void balance(node *n) {
	if(n->left == NULL) return;
	if(n->left->subtreeSize * 2 < n->right->subtreeSize) {
		node *temp = new node();
		temp->left = n->left;
		temp->right = n->right->left;
		temp->subtreeSize = temp->left->subtreeSize + temp->right->subtreeSize;
		n->left = temp;
		n->right = n->right->right;
	} else if(n->right->subtreeSize * 2 < n->left->subtreeSize) {
		node *temp = new node();
		temp->right = n->right;
		temp->left = n->left->right;
		temp->subtreeSize = temp->right->subtreeSize + temp->left->subtreeSize;
		n->right = temp;
		n->left = n->left->left;
	}
}

node* getAtIdx(node *n, int idx, int curIdx) {
	if(n->left == NULL) return n;

	if(curIdx + n->left->subtreeSize <= idx) {
		return getAtIdx(n->right, idx, curIdx+n->left->subtreeSize);
	} else {
		return getAtIdx(n->left, idx, curIdx);
	}

}

void addAtIdx(node *n, int id, int idxToAdd, int curIdx) {
	if(n->left==NULL) {
		if(n->val == -1) {
			n->val = id;
		} else {
			if(curIdx == idxToAdd) {
				n->left = new node();
				n->left->val = id;
				n->right = new node();
				n->right->val = n->val;
				n->val = -2;
			} else {
				n->right = new node();
				n->right->val = id;
				n->left = new node();
				n->left->val = n->val;
				n->val = -2;
			}
			n->subtreeSize = n->left->subtreeSize + n->right->subtreeSize;
		}
	} else {
		if(curIdx + n->left->subtreeSize <= idxToAdd) {
			addAtIdx(n->right, id, idxToAdd, curIdx+n->left->subtreeSize);
		} else {
			addAtIdx(n->left, id, idxToAdd, curIdx);
		}
			n->subtreeSize = n->left->subtreeSize + n->right->subtreeSize;
	}

	balance(n);
}

node root = *(new node);
void addNode(int idxToAdd, int sizeToAdd) {
	node *temp = getAtIdx(&root, idxToAdd, 0);
	if(temp->val==-1) temp->val = 1;
	for(int i = 1; i <= sizeToAdd; i++) {
		AdjList[temp->val].push_back(curNode+i);
	}
	temp->val = ++curNode;
	for(int i = 1; i < sizeToAdd; i++) {
		addAtIdx(&root, ++curNode, idxToAdd+i, 0);
	}
}

int curActualIdx = 0;
int depth[200005];
int kthAncestor[20][200005];
void getDepth(int u, int d) {
	// cerr << u << ": " << d << endl;
	depth[u] = d;
	if(AdjList[u].empty()) {
		sz[u] = 1;
		actualIdxToNode[curActualIdx] = u;
		nodeToActualIdx[u] = curActualIdx++;
		return;
	}
	for(auto v: AdjList[u]) {
		sz[u] += sz[v];
		kthAncestor[0][v] = u;
		getDepth(v, d-1);
	}
}

void calcKthAncestor() {
	kthAncestor[0][1] = 0;
	for(int i = 1+1; i <= curNode; i++)
		for(int j = 1; j < 20; j++) {
			kthAncestor[j][i] = kthAncestor[j-1][kthAncestor[j-1][i]];
			if(kthAncestor[j][i]==0) break;
		}
}

int lca(int a, int b) {
	if(depth[a] < depth[b])
		for(int j = 31-__builtin_clz(C-depth[a]); j >= 0; j--)
			if(depth[a] + (1<<j) <= depth[b])
				a = kthAncestor[j][a];
	if(depth[b] < depth[a])
		for(int j = 31-__builtin_clz(C-depth[b]); j >= 0; j--)
			if(depth[b] + (1<<j) <= depth[a])
				b = kthAncestor[j][b];
	for(int j = 31-__builtin_clz(C-depth[a]); j >= 0; j--)
		if(kthAncestor[j][a] != kthAncestor[j][b]) {
			a = kthAncestor[j][a];
			b = kthAncestor[j][b];
		}
	if(a != b) {
		a = kthAncestor[0][a];
		b = kthAncestor[0][b];
	}
	return a;
}

int closestToLeft[100005];
int closestToRight[100005];

int GetBestPosition(int N_, int C_, int R_, int *K_, int *S_, int *E_) {
	N=N_, C=C_, R=R_;
	K=K_, S=S_, E=E_;
	sz[1] = 1;
	for(int i = C-1; i >= 0; i--) {
		addNode(S[i], E[i]-S[i]+1);
	}

	for(int i = 0; i < N; i++) {
		node *temp = getAtIdx(&root, i, 0);
		actualIdxToNode[i] = temp->val;
		nodeToActualIdx[temp->val] = i;
		// cerr << temp->val << " ";
	}
	// cerr << endl;

	getDepth(1,C);
	calcKthAncestor();

	closestToLeft[0] = -1;
	for(int i = 1; i <= N; i++) {
		closestToLeft[i] = closestToLeft[i-1];
		if(K[i-1] > R)
			closestToLeft[i] = i-1;
	}

	closestToRight[N-1] = -1;
	for(int i = N-1-1; i >= 0; i--) {
		closestToRight[i] = closestToRight[i+1];
		if(K[i+1-1] > R)
			closestToRight[i] = i+1;
	}


	int ans = -1;
	int pos = -1;
	for(int i = 0; i < N; i++) {
		int a = 0;
		if(closestToLeft[i] == -1) {
			a = C-depth[actualIdxToNode[i]];
		} else {
			a = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToLeft[i]])]-depth[actualIdxToNode[i]]-1;
		}
		int b = 0;
		if(closestToRight[i] == -1) {
			b = C-depth[actualIdxToNode[i]];
		} else {
			b = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToRight[i]])]-depth[actualIdxToNode[i]]-1;
		}

		if(min(a,b) > ans) {
			ans = min(a,b);
			pos = i;
		}
	}

	return pos;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51