Submission #380842

#	Time	Username	Problem	Language	Result	Execution time	Memory
380842		VodkaInTheJar	popa (BOI18_popa)	C++14	61 / 100	861 ms	604 KiB

popa

#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, 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, i, i))
				low = mid;
				
				else 
				high = mid-1;
			}
			
			nxt_l[i] = low;
		}
		
		if (i == n-1 || query(i, 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, 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: 37 / 37
• Subtask 2: 24 / 24
• Subtask 3: 0 / 39