# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1086294 | RiverFlow | Horses (IOI15_horses) | C++14 | 1593 ms | 12180 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
const int N = (int)5e5 + 7;
const int mod = (int)1e9 + 7;
int add(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
int sub(int a, int b) { return a >= b ? a - b : a - b + mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int n, x[N], y[N];
#define nl "\n"
#define ll long long
const ll LIM = (int)1e10;
bool isSub2 = 1;
int fx() {
ll mx = 0;
int ans = 0;
if (isSub2) {
int p = 0;
if (n > 36) p = n - 36;
FOD(i, n - 1, p) {
if (y[i] >= mx) {
ans = i;
}
mx = max(mx, (ll)y[i]);
mx = min(LIM, mx * x[i]);
}
return ans;
}
FOD(i, n - 1, 0) {
if (y[i] >= mx) {
ans = i;
}
mx = max(mx, (ll)y[i]);
mx = min(LIM, mx * x[i]);
}
return ans;
}
int init(int N, int X[], int Y[]) {
n = N;
FOR(i, 0, n - 1) x[i] = X[i], y[i] = Y[i];
isSub2 &= *min_element(x, x + n) >= 2;
int px = fx(), ans = 1;
FOR(i, 0, px) ans = mul(ans, x[i]);
return mul(ans, y[px]);
}
// khi thay doi X -> nhan p(i >= pos) *= X'/X
// khi thay doi Y ->
int updateX(int pos, int val) {
isSub2 &= val >= 2;
x[pos] = val;
int px = fx(), ans = 1;
FOR(i, 0, px) ans = mul(ans, x[i]);
return mul(ans, y[px]);
}
int updateY(int pos, int val) {
y[pos] = val;
int px = fx(), ans = 1;
FOR(i, 0, px) ans = mul(ans, x[i]);
return mul(ans, y[px]);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |