oj.uz

Submission #579738

# Submission time Handle Problem Language Result Execution time Memory
579738 2022-06-19T17:38:36 Z AlperenT popa (BOI18_popa) C++17
100 / 100
 321 ms 20560 KB 
#include <bits/stdc++.h>
#include <popa.h>

using namespace std;

const int N = 1000 + 5;

int n, rangeroot[N][N];

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

bitset<N> divright[N], revdivright[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++) divright[i].reset(), revdivright[i].reset(), rightgood[i].reset();

	stack<int> 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;

		rightgood[i][i] = 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 = (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(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 27 ms 20048 KB Output is correct
2 Correct 26 ms 20048 KB Output is correct
3 Correct 30 ms 20096 KB Output is correct
4 Correct 29 ms 20048 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 20488 KB Output is correct
2 Correct 307 ms 20560 KB Output is correct
3 Correct 179 ms 20432 KB Output is correct
4 Correct 307 ms 20548 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 20492 KB Output is correct
2 Correct 321 ms 20552 KB Output is correct
3 Correct 312 ms 20484 KB Output is correct
4 Correct 283 ms 20488 KB Output is correct