Submission #1116582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116582		mmk	Xylophone (JOI18_xylophone)	C++17	47 / 100	202 ms	1796 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;

int a[5010];

map<pair<int,int>,int> marc;

int q(int ini, int fim)
{
	if(marc[{ini,fim}] != 0)
		return marc[{ini,fim}];
	else
		return marc[{ini,fim}] = query(ini,fim);
}

int find(int x)
{
	int cur = 0;

	while((1 << cur) <= x)
	cur++;
	return (cur - 1);
}

void solveL(int ini, int  fim, int type);
void solveR(int ini, int fim, int type);
//resolve o intervalo [ini,menor]
//0 -> fim == menor
//1 -> fim == maior
void solveL(int ini, int fim, int type)
{
	if(ini == fim) return;
	if(fim - ini == 1 && a[ini] != 0) return;
	int dif = q(ini,fim);

	if(fim - ini == 1)
	{
		if(a[ini] != 0) return;
		if(type == 0)
			a[ini] = a[fim] + dif;
		else
			a[ini] = a[fim] - dif;
		return;
	}

	int l = ini, r = fim;

	while(l < r)
	{
		int m = (l + r + 1)/2;

		if(q(m,fim) == dif) l = m;
		else r = m-1;
	}

	if(type == 0)
	{
		int maior = l;
		a[maior] = a[fim] + dif;

		int m = find(fim - maior + 1);

		solveL(ini,maior,1);
		solveR(maior,maior + m - 1,1);
		solveL(maior + m,fim,0);
	}
	else
	{
		int menor = l;
		a[menor] = a[fim] - dif;

		int m = find(fim - menor + 1);

		solveL(ini,menor,0);
		solveR(menor,menor + m - 1,0);
		solveL(menor + m,fim,1);
	}
}

void solveR(int ini, int fim, int type)
{
	if(ini == fim) return;
	if(fim - ini == 1 && a[fim] != 0) return;
	int dif = q(ini,fim);

	if(fim - ini == 1)
	{
		if(a[fim] != 0) return;
		if(type == 0)
			a[fim] = a[ini] + dif;
		else
			a[fim] = a[ini] - dif;
		return;
	}

	int l = ini, r = fim;

	while(l < r)
	{
		int m = (l + r - 1)/2;

		if(q(ini,m) == dif) r = m;
		else l = m+1;
		// cerr << l << " " << r << " " << m << "||\n";
	}

	if(type == 0)
	{
		int maior = r;
		a[maior] = a[ini] + dif;

		int m = find(maior - ini + 1);

		solveR(ini,ini + m - 0,0);
		solveL(ini + m,maior,1);
		solveR(maior,fim,1);
	}
	else
	{
		int menor = r;
		a[menor] = a[ini] - dif;

		int m = find(menor - ini + 1);

		solveR(ini,ini + m - 0,1);
		solveL(ini + m,menor,0);
		solveR(menor,fim,0);
	}
}


void solve(int N)
{
	int l = 1, r = N;

	while(l < r)
	{
		int m = (l + r - 1)/2;

		if(q(1,m) == N - 1) r = m;
		else l = m + 1;
	}

	int maior = r;

	l = 1, r = maior;

	while(l < r)
	{
		int m = (l + r + 1)/2;

		if(q(m,N) == N - 1) l = m;
		else r = m - 1;
	}

	int menor = l;

	a[menor] = 1;
	a[maior] = N;

	// cerr << "penis\n";
	solveL(1,menor,0);

	int m = find(maior - menor + 1);
	// int m = maior - menor;
	solveR(menor,menor + m - 1,0);

	solveL(menor + m,maior,1);

	solveR(maior,N,1);


	for(int i = 1; i <= N; i++)
	{
		// cerr << i << " " << a[i] << "||\n";
		answer(i,a[i]);
	}


}

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 0 / 53