Submission #1281600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281600		SSKMF	Horses (IOI15_horses)	C++20	54 / 100	95 ms	28776 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

const int mod(1000000007);
struct Nod { int prefix = 1 , sufix = 1 , indice_maxim = 0 , maxim = 0 , total = 1; } arbore[1000000];
int lungime , factor_1[500001] , factor_2[500001];

inline void Combina (Nod& rezultat , Nod& stanga , Nod& dreapta)
{
	rezultat.total = 1LL * stanga.total * dreapta.total % mod;
	
	if (factor_2[stanga.indice_maxim] > min(1000000001LL , min(1000000001LL , 1LL * stanga.sufix * factor_2[dreapta.indice_maxim]) * dreapta.prefix))
	{
		rezultat.prefix = stanga.prefix;
		rezultat.sufix = min(1000000001LL , min(1000000001LL , 1LL * stanga.sufix * dreapta.prefix) * dreapta.sufix);
		rezultat.indice_maxim = stanga.indice_maxim;
		rezultat.maxim = stanga.maxim;
	}
	else
	{
		rezultat.prefix = min(1000000001LL , min(1000000001LL , 1LL * stanga.prefix * dreapta.sufix) * dreapta.prefix);
		rezultat.sufix = dreapta.sufix;
		rezultat.indice_maxim = dreapta.indice_maxim;
		rezultat.maxim = 1LL * stanga.total * dreapta.maxim % mod;
	}
}

inline void Build (const int nod , const int stanga , const int dreapta)
{
	if (stanga == dreapta)
	{
		arbore[nod].prefix = factor_1[stanga];
		arbore[nod].sufix = 1;
		arbore[nod].indice_maxim = stanga;
		arbore[nod].maxim = 1LL * factor_1[stanga] * factor_2[stanga] % mod;
		arbore[nod].total = factor_1[stanga];
		return;
	}

	const int mijloc = (stanga + dreapta) >> 1;
	Build(nod + 1 , stanga , mijloc);
	Build(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta);
	Combina(arbore[nod] , arbore[nod + 1] , arbore[nod + ((mijloc - stanga + 1) << 1)]);
}

inline void Update (const int nod , const int stanga , const int dreapta , const int indice)
{
	if (stanga == dreapta)
	{
		arbore[nod].prefix = factor_1[stanga];
		arbore[nod].sufix = 1;
		arbore[nod].indice_maxim = stanga;
		arbore[nod].maxim = 1LL * factor_1[stanga] * factor_2[stanga] % mod;
		arbore[nod].total = factor_1[stanga];
		return;
	}

	const int mijloc = (stanga + dreapta) >> 1;
	if (indice <= mijloc) { Update(nod + 1 , stanga , mijloc , indice); }
	else { Update(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta , indice); }
	Combina(arbore[nod] , arbore[nod + 1] , arbore[nod + ((mijloc - stanga + 1) << 1)]);
}

int init (int __lungime , int __factor_1[] , int __factor_2[])
{
	lungime = __lungime;
	for (int indice = 1 ; indice <= lungime ; indice++)
		{ factor_1[indice] = __factor_1[indice - 1]; factor_2[indice] = __factor_2[indice - 1]; }

	Build(1 , 1 , lungime);
	return arbore[1].maxim;
}

int updateX (int indice , int valoare)
{	
	factor_1[indice + 1] = valoare;
	Update(1 , 1 , lungime , indice + 1); 
	return arbore[1].maxim;
}

int updateY (int indice , int valoare)
{
	factor_2[indice + 1] = valoare;
	Update(1 , 1 , lungime , indice + 1); 
	return arbore[1].maxim;
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23