oj.uz

Submission #1116555

# Submission time Handle Problem Language Result Execution time Memory
1116555 2024-11-21T19:49:32 Z mmk Xylophone (JOI18_xylophone) C++17
0 / 100
 1 ms 336 KB 
#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);

	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);

	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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -