oj.uz

Submission #380841

# Submission time Handle Problem Language Result Execution time Memory
380841 2021-03-23T09:08:52 Z VodkaInTheJar popa (BOI18_popa) C++14
0 / 100
 186 ms 492 KB 
#include <bits/stdc++.h>
#include "popa.h"

using namespace std;

int find_root(int l, int r, vector <int> &nxt_l, vector <int> &nxt_r)
{
	for (int i = l; i <= r; i++)
	if (nxt_l[i] < l && nxt_r[i] > r)
	return i;
	
	assert(0);
}

int f(int l, int r, int *left, int *right, vector <int> &nxt_l, vector <int> &nxt_r)
{
	if (l > r)
	return -1; 
	
	int root = find_root(l, r, nxt_l, nxt_r);
	left[root] = f(l, root-1, left, right, nxt_l, nxt_r);
	right[root] = f(root+1, r, left, right, nxt_l, nxt_r);
	
	return root;
}

int solve(int n, int *left, int *right)
{
	vector <int> nxt_l(n), nxt_r(n);
	for (int i = 0; i < n; i++)
	{
		if (i == 0 || query(0, i-1, i, i))
		nxt_l[i] = -1; 
		
		else 
		{
			int low = 0, high =	i-1;
			while (low < high)
			{
				int mid = (low + high + 1) / 2;
				if (!query(mid, i-1, i, i))
				low = mid;
				
				else 
				high = mid-1;
			}
			
			nxt_l[i] = low;
		}
		
		if (i == n-1 || query(i+1, n-1, i, i))
		nxt_r[i] = n;
		
		else 
		{
			int low = i+1, high = n-1;
			while (low < high)
			{
				int mid = (low + high) / 2;
				if (!query(i+1, mid, i, i))
				high = mid;
				
				else 
				low = mid+1;
			}
			
			nxt_r[i] = low;
		}
	}
	
	return f(0, n-1, left, right, nxt_l, nxt_r);
}

Subtask #1
0 / 37.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 492 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 19 ms 364 KB too many queries
2 Halted 0 ms 0 KB -