oj.uz

Submission #579733

# Submission time Handle Problem Language Result Execution time Memory
579733 2022-06-19T17:07:08 Z AlperenT popa (BOI18_popa) C++17
61 / 100
 488 ms 20940 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];

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.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 20048 KB Output is correct
2 Correct 29 ms 20076 KB Output is correct
3 Correct 37 ms 20048 KB Output is correct
4 Correct 42 ms 20048 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 20940 KB Output is correct
2 Correct 476 ms 20872 KB Output is correct
3 Correct 266 ms 20876 KB Output is correct
4 Correct 474 ms 20932 KB Output is correct

Subtask #3
0 / 39.0

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