# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1192395 | lance0 | Horses (IOI15_horses) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
long long fast_expo(long long x, long long y, long long mod) {
long long ans = 1;
long long mult = x;
while (y > 0) {
if (y % 2) {
ans = (ans*mult) % mod;
}
mult = (mult*mult) % mod;
y = y >> 1;
}
return ans;
}
long long inv_mod(long long x, long long mod) {
return fast_expo(x, mod-1, mod);
}
int n;
vector<long long> x, y;
long long product = 1;
long long mod = 1e9+7;
long long init(int N, long long X[], long long Y[]) {
n = N;
for (int i = 0; i < n; i++) {
x.push_back(X[i]);
product = (product * X[i]) % mod;
}
for (int i = 0; i < n; i++) {
y.push_back(Y[i]);
}
long long picked_y = y[n-1];
long long divisor = x[n-1];
long long curr_y = y[n-1];
long long curr_div = x[n-1];
for (int i = n-2; i > 0; i--) {
curr_div *= x[i];
curr_y = y[i];
if ((curr_y * divisor) > (picked_y * curr_div)) {
picked_y = curr_y;
divisor = curr_div;
}
if (curr_div >= 1e9) {
break;
}
}
long long ans = ((product * picked_y) % mod * inv_mod(divisor, mod)) % mod;
return ans;
}
long long updateX(int pos, long long val) {
product = (((product * val) % mod) * inv_mod(x[pos], mod))% mod;
x[pos] = val;
long long picked_y = y[n-1];
long long divisor = x[n-1];
long long curr_y = y[n-1];
long long curr_div = x[n-1];
for (int i = n-2; i > 0; i--) {
curr_div *= x[i];
curr_y = y[i];
if ((curr_y * divisor) > (picked_y * curr_div)) {
picked_y = curr_y;
divisor = curr_div;
}
if (curr_div >= 1e9) {
break;
}
}
long long ans = ((product * picked_y) % mod * inv_mod(divisor, mod)) % mod;
return ans;
}
long long updateY(int pos, long long val) {
y[pos] = val;
long long picked_y = y[n-1];
long long divisor = x[n-1];
long long curr_y = y[n-1];
long long curr_div = x[n-1];
for (int i = n-2; i > 0; i--) {
curr_div *= x[i];
curr_y = y[i];
if ((curr_y * divisor) > (picked_y * curr_div)) {
picked_y = curr_y;
divisor = curr_div;
}
if (curr_div >= 1e9) {
break;
}
}
long long ans = ((product * picked_y) % mod * inv_mod(divisor, mod)) % mod;
return ans;
}