oj.uz

Submission #579719

# Submission time Handle Problem Language Result Execution time Memory
579719 2022-06-19T16:41:19 Z AlperenT popa (BOI18_popa) C++17
0 / 100
 100 ms 42056 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));
	memset(divleft, 0, sizeof(divleft)), memset(divright, 0, sizeof(divright)), memset(revdivleft, 0, sizeof(revdivleft)), memset(revdivright, 0, sizeof(revdivright));
	memset(leftgood, 0, sizeof(leftgood)), memset(rightgood, 0, sizeof(rightgood));

	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];
}

Compilation message

popa.cpp: In function 'int solve(int, int*, int*)':
popa.cpp:38:36: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type 'class std::bitset<1005>'; use assignment or value-initialization instead [-Wclass-memaccess]
   38 |  memset(divleft, 0, sizeof(divleft)), memset(divright, 0, sizeof(divright)), memset(revdivleft, 0, sizeof(revdivleft)), memset(revdivright, 0, sizeof(revdivright));
      |                                    ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:66,
                 from popa.cpp:1:
/usr/include/c++/10/bitset:751:11: note: 'class std::bitset<1005>' declared here
  751 |     class bitset
      |           ^~~~~~
popa.cpp:38:75: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type 'class std::bitset<1005>'; use assignment or value-initialization instead [-Wclass-memaccess]
   38 |  memset(divleft, 0, sizeof(divleft)), memset(divright, 0, sizeof(divright)), memset(revdivleft, 0, sizeof(revdivleft)), memset(revdivright, 0, sizeof(revdivright));
      |                                                                           ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:66,
                 from popa.cpp:1:
/usr/include/c++/10/bitset:751:11: note: 'class std::bitset<1005>' declared here
  751 |     class bitset
      |           ^~~~~~
popa.cpp:38:118: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type 'class std::bitset<1005>'; use assignment or value-initialization instead [-Wclass-memaccess]
   38 |  memset(divleft, 0, sizeof(divleft)), memset(divright, 0, sizeof(divright)), memset(revdivleft, 0, sizeof(revdivleft)), memset(revdivright, 0, sizeof(revdivright));
      |                                                                                                                      ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:66,
                 from popa.cpp:1:
/usr/include/c++/10/bitset:751:11: note: 'class std::bitset<1005>' declared here
  751 |     class bitset
      |           ^~~~~~
popa.cpp:38:163: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type 'class std::bitset<1005>'; use assignment or value-initialization instead [-Wclass-memaccess]
   38 |  memset(divleft, 0, sizeof(divleft)), memset(divright, 0, sizeof(divright)), memset(revdivleft, 0, sizeof(revdivleft)), memset(revdivright, 0, sizeof(revdivright));
      |                                                                                                                                                                   ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:66,
                 from popa.cpp:1:
/usr/include/c++/10/bitset:751:11: note: 'class std::bitset<1005>' declared here
  751 |     class bitset
      |           ^~~~~~
popa.cpp:39:38: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type 'class std::bitset<1005>'; use assignment or value-initialization instead [-Wclass-memaccess]
   39 |  memset(leftgood, 0, sizeof(leftgood)), memset(rightgood, 0, sizeof(rightgood));
      |                                      ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:66,
                 from popa.cpp:1:
/usr/include/c++/10/bitset:751:11: note: 'class std::bitset<1005>' declared here
  751 |     class bitset
      |           ^~~~~~
popa.cpp:39:79: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type 'class std::bitset<1005>'; use assignment or value-initialization instead [-Wclass-memaccess]
   39 |  memset(leftgood, 0, sizeof(leftgood)), memset(rightgood, 0, sizeof(rightgood));
      |                                                                               ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:66,
                 from popa.cpp:1:
/usr/include/c++/10/bitset:751:11: note: 'class std::bitset<1005>' declared here
  751 |     class bitset
      |           ^~~~~~

Subtask #1
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 25796 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 100 ms 42056 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 24 ms 20816 KB too many queries
2 Halted 0 ms 0 KB -