Submission #579733

#	Time	Username	Problem	Language	Result	Execution time	Memory
579733		AlperenT	popa (BOI18_popa)	C++17	61 / 100	488 ms	20940 KiB

popa

#include <bits/stdc++.h>
#include <popa.h>

using namespace std;

const int N = 1000 + 5;

int testarr[N];

int n, rangeroot[N][N];

pair<int, int> leftchild[N][N], rightchild[N][N];

bitset<N> divleft[N], divright[N], revdivleft[N], revdivright[N], leftgood[N], rightgood[N];

int maketree(int l, int r, int* left, int* right){
	if(l != -1 && r != -1 && l <= r){
		int root = rangeroot[l][r];

		left[root] = maketree(leftchild[l][r].first, leftchild[l][r].second, left, right);
		right[root] = maketree(rightchild[l][r].first, rightchild[l][r].second, left, right);

		return root;
	}
	else return -1;
}

int solve(int n_, int* left, int* right){
	n = n_;

	memset(rangeroot, -1, sizeof(rangeroot)), memset(leftchild, -1, sizeof(leftchild)), memset(rightchild, -1, sizeof(rightchild));

	for(int i = 0; i < n; i++) divleft[i].reset(), divright[i].reset(), revdivleft[i].reset(), revdivright[i].reset(), leftgood[i].reset(), rightgood[i].reset();

	stack<int> stk;

	stk.push(-1);

	for(int i = 0; i < n; i++){
		while(stk.top() != -1 && query(stk.top(), i, i, i)) stk.pop();

		for(int j = stk.top() + 1; j <= i; j++) divleft[i][j] = true;

		stk.push(i);
	}

	for(int l = 0; l < n; l++){
		for(int r = l; r < n; r++){
			if(divleft[r][l]) revdivleft[l][r] = true;
		}
	}

	stk = {};

	stk.push(n);

	for(int i = n - 1; i >= 0; i--){
		while(stk.top() != n && query(i, i, i, stk.top())) stk.pop();

		for(int j = stk.top() - 1; j >= i; j--) divright[i][j] = true;

		stk.push(i);
	}

	for(int r = 0; r < n; r++){
		for(int l = 0; l <= r; l++){
			if(divright[l][r]) revdivright[r][l] = true;
		}
	}

	for(int i = 0; i < n; i++){
		rangeroot[i][i] = i;

		leftgood[i][i] = rightgood[i][i] = true;
		if(i + 1 < n) leftgood[i][i + 1] = true;
		if(i - 1 >= 0) rightgood[i][i - 1] = true;
	}

	for(int len = 2; len <= n; len++){
		for(int l = 0; l + len - 1 < n; l++){
			int r = l + len - 1;

			bitset<N> roots = (revdivleft[l] & leftgood[l]) & (revdivright[r] & rightgood[r]);

			if(roots.count()){
				int root = roots._Find_first();

				rangeroot[l][r] = root;

				if(root - 1 >= l) leftchild[l][r] = {l, root - 1};
				if(root + 1 <= r) rightchild[l][r] = {root + 1, r};

				if(r + 1 < n) leftgood[l][r + 1] = true;
				if(l - 1 >= 0) rightgood[r][l - 1] = true;
			}
		}
	}

	return maketree(0, n - 1, left, right);
}

• Subtask 1: 37 / 37
• Subtask 2: 24 / 24
• Subtask 3: 0 / 39