oj.uz

Submission #579721

# Submission time Handle Problem Language Result Execution time Memory
579721 2022-06-19T16:46:06 Z AlperenT popa (BOI18_popa) C++17
0 / 100
 110 ms 42064 KB 
#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];

void maketree(int l, int r, int* left, int* right){
	if(l > r) return;

	int root = rangeroot[l][r];

	if(leftchild[l][r] != pair{-1, -1}){
		left[root] = rangeroot[leftchild[l][r].first][leftchild[l][r].second];
		maketree(leftchild[l][r].first, leftchild[l][r].second, left, right);
	}
	else left[root] = -1;

	if(rightchild[l][r] != pair{-1, -1}){
		right[root] = rangeroot[rightchild[l][r].first][rightchild[l][r].second];
		maketree(rightchild[l][r].first, rightchild[l][r].second, left, right);
	}
	else right[root] = -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;
			}
		}
	}

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

	return rangeroot[0][n - 1];
}

Subtask #1
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 38084 KB Execution killed with signal 15
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 110 ms 42064 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 20816 KB too many queries
2 Halted 0 ms 0 KB -