Submission #1326336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326336		farica	Horses (IOI15_horses)	C++20	0 / 100	28 ms	12964 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define se second
#define fi first

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int MOD = 1e9 + 7;
const int B = 32;
const int C = 1e9;

int n, m, pref;
vector<ll> vec, x, y;
	
ll exp(ll a, ll b) {
	assert(b >= 0);
	a %= MOD;  // note: m * m must be less than 2^63 to avoid ll overflow
	ll res = 1;
	while (b > 0) {
		if (b % 2 == 1) { res = res * a % MOD; }
		a = a * a % MOD;
		b /= 2;
	}
	return res;
}
	
int calc() {
	ll prev = 1, ans = 0;
	int cnt = n-m;
	for(int i=n-1; i>=n-m; --i) {
		prev *= x[i];
		if(prev >= C) { 
			cnt = i;
			break;
		}
	}
	prev = 1;
	for(int i=cnt+1; i<n; ++i) {
		prev *= x[i];
		ll tmp = prev * y[i];
		ans = max(ans,tmp);
	}
	ans %= MOD;
	for(int i=n-m; i<=cnt; ++i) ans = (1ll * ans * x[i]) % MOD;
	ans = (1ll * ans * pref) % MOD;
	return ans;
}	
	
int init(int N, int X[], int Y[]) {
	x.resize(N);
	y.resize(N);
	n = N;
	for(int i=0; i<N; ++i) {
		x[i] = X[i];
		y[i] = Y[i];
	}
	if(N < B) m = N;
	else m = B;
	pref = 1;
	for(int i=0; i<N-m; ++i) pref = (1ll * pref * X[i]) % MOD;
	vec.resize(m);
	return calc();
}

int updateX(int pos, int val) {	
	if(pos < n-m) {
		pref = (1ll * pref * exp(x[pos], MOD-2));
		pref = (1ll * pref * val);
	}
	x[pos] = val;
	return calc();
}

int updateY(int pos, int val) {
	y[pos] = val;
	return calc();
}

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