Submission #1116564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116564		mmk	Xylophone (JOI18_xylophone)	C++17	47 / 100	196 ms	1748 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);
}

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

	if(fim - ini == 1)
	{
		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;

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

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

void solveR(int ini, int fim, int type)
{
	if(ini == fim) return;
	int dif = q(ini,fim);

	if(fim - ini == 1)
	{
		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;

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

		solveR(ini,menor - 1,1);
		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);
	solveR(menor,maior-1,0);
	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