Submission #1184859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184859		stdfloat	Horses (IOI15_horses)	C++20	37 / 100	77 ms	9032 KiB

horses

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

using ll = long long;

const int md = (int)1e9 + 7;

int n, Z = 1;

vector<int> x(n), y(n);

int pw(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = (ll)res * x % md;
	
		y >>= 1;
		x = (ll)x * x % md;
	}

	return res;
}

int init(int N, int a[], int b[]) {
	n = N;
	x = y = vector<int>(n);
	for (int i = 0; i < n; i++) {
		x[i] = a[i]; y[i] = b[i];
	}

	for (int i = 0; i < max(n - 60, 0); i++)
		Z = (ll)Z * x[i] % md;

	ll pr = 1;
	int X = Z, ans = 0, lst = -1;
	for (int i = max(n - 60, 0); i < n; i++) {
		pr *= x[i];

		if (md < pr || !~lst || y[lst] < pr * y[i]) {
			X = (ll)X * (pr % md) % md; pr = 1;

			ans = (ll)X * y[i] % md; lst = i;
		}
	}

	return ans;
}

int updateX(int pos, int val) {
	if (pos < max(n - 60, 0)) Z = ((ll)Z * pw(x[pos], md - 2) % md) * val % md;
	x[pos] = val;

	ll pr = 1;
	int X = Z, ans = 0, lst = -1;
	for (int i = max(n - 60, 0); i < n; i++) {
		pr *= x[i];

		if (md < pr || !~lst || y[lst] < pr * y[i]) {
			X = (ll)X * (pr % md) % md; pr = 1;

			ans = (ll)X * y[i] % md; lst = i;
		}
	}

	return ans;
}

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

	ll pr = 1;
	int X = Z, ans = 0, lst = -1;
	for (int i = max(n - 60, 0); i < n; i++) {
		pr *= x[i];

		if (md < pr || !~lst || y[lst] < pr * y[i]) {
			X = (ll)X * (pr % md) % md; pr = 1;

			ans = (ll)X * y[i] % md; lst = i;
		}
	}

	return ans;
}

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