Submission #137970

#	Time	Username	Problem	Language	Result	Execution time	Memory
137970		arthurconmy	Horses (IOI15_horses)	C++14	54 / 100	1566 ms	16100 KiB

horses

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

using ll=long long;

const int p = 1000000007;
const int pLL = 1000000007LL;
const int MAXN = 500001; // 1-index that shit
const ll MAXP = 1000000000;

int n;
ll X[MAXN];
ll Y[MAXN];
ll x_prod=1;

int gcd(int a, int b, int &x, int &y)
{
	if(a%b == 1) // uh ... plug a = p in the real thing I guess then
	{
		x = 1;
		y = -int(a/b);

		return 1;
	}

	int d = gcd(b,a%b,x,y); 
	int old_x = x;

	x = y;
	y = old_x - int(a/b)*y;

	return d;
}

ll mod_inv(ll x_raw)
{
	x_raw %= pLL;
	int x = int(x_raw);

	if(x==1) return 1; // thonking

	int x1=-1; 
	int y1=-1;
	
	gcd(p,x,x1,y1); // EDITING THIS DAMN FUNCTION !!!

	while(y1<0) y1+=p;

	return ll(y1);
}

pair<ll,ll> mexico(pair<ll,ll> a, pair<ll,ll> b)
{
	if(a.first*b.second >= a.second*b.first) return a;
	return b;
}

int init(int N, int x[], int y[])
{
	n=N;

	for(int i=0; i<n; i++)
	{
		X[i+1]=ll(x[i]);

		x_prod *= ll(x[i]);
		x_prod %= pLL;
	}

	for(int i=0; i<n; i++)
	{
		Y[i+1]=ll(y[i]);
	}	

	pair<ll,ll> GL = {ll(Y[n]),1LL}; // gain and loss

	ll cur_loss = 1LL;

	for(int i=n-1; i>=1; i--)
	{
		cur_loss *= X[i+1];
		if(cur_loss>MAXP) break;

		GL = mexico(GL, make_pair(ll(Y[i]),cur_loss));
	}

	// return x_prod * GL.first * mod_inv(GL.second)

	ll ans = x_prod * GL.first;
	ans %= pLL;
	ans *= mod_inv(int(GL.second)%p);
	ans %= pLL;

	return int(ans); 
}

int updateX(int pos, int val)
{
	pos++;

	x_prod *= ll(mod_inv(X[pos]));
	x_prod %= pLL;
	x_prod *= val;
	x_prod %= pLL;

	X[pos]=val;

	pair<ll,ll> GL = {ll(Y[n]),1LL}; // gain and loss

	ll cur_loss = 1LL;

	for(int i=n-1; i>=1; i--)
	{
		cur_loss *= X[i+1];
		if(cur_loss>MAXP) break;

		GL = mexico(GL, make_pair(ll(Y[i]),cur_loss));
	}

	// return x_prod * GL.first * mod_inv(GL.second)

	ll ans = x_prod * GL.first;
	ans %= pLL;
	ans *= mod_inv(int(GL.second)%p);
	ans %= pLL;

	return int(ans);
}

int updateY(int pos, int val)
{
	Y[++pos]=val;

	pair<ll,ll> GL = {ll(Y[n]),1LL}; // gain and loss

	ll cur_loss = 1LL;

	for(int i=n-1; i>=1; i--)
	{
		cur_loss *= X[i+1];
		if(cur_loss>MAXP) break;

		GL = mexico(GL, make_pair(ll(Y[i]),cur_loss));
	}

	// return x_prod * GL.first * mod_inv(GL.second)

	ll ans = x_prod * GL.first;
	ans %= pLL;
	ans *= mod_inv(int(GL.second)%p);
	ans %= pLL;

	return int(ans); 
}

#ifdef ARTHUR_LOCAL

	int X_raw[MAXN-1];
	int Y_raw[MAXN-1];

	int main()
	{
		X_raw[0]=2;
		X_raw[1]=1;
		X_raw[2]=3;
		Y_raw[0]=3;
		Y_raw[1]=4;
		Y_raw[2]=1;

		cout << init(3,X_raw,Y_raw) << endl;
		cout << updateY(1,2) << endl;
	}
#endif

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