| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 387323 | aarr | Horses (IOI15_horses) | C++14 | 0 ms | 0 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 int long long
const int N = 500 * 1000 + 5, mod = 1000 * 1000 * 1000 + 7;
int n;
long long seg1[N * 4];
int seg2[N * 4];
set <int, greater<int> > s;
int a[N], b[N];
void update1(int p, int val, int id = 1, int s = 0, int e = n) {
if (e - s == 1) {
seg1[id] = val;
return;
}
int md = (s + e) / 2;
if (p < md) {
update1(p, val, id * 2, s, md);
}
else {
update1(p, val, id * 2 + 1, md, e);
}
seg1[id] = (seg1[id * 2] * seg1[id * 2 + 1]) % mod;
}
void update2(int p, int val, int id = 1, int s = 0, int e = n) {
if (e - s == 1) {
seg2[id] = val;
return;
}
int md = (s + e) / 2;
if (p < md) {
update2(p, val, id * 2, s, md);
}
else {
update2(p, val, id * 2 + 1, md, e);
}
seg2[id] = max(seg2[id * 2], seg2[id * 2 + 1]);
}
long long get1(int l, int r, int id = 1, int s = 0, int e = n) {
if (r <= s || e <= l) {
return 1;
}
if (l <= s && e <= r) {
return seg1[id];
}
int md = (s + e) / 2;
return (1ll * get1(l, r, id * 2, s, md) * get1(l, r, id * 2 + 1, md, e)) % mod;
}
int get2(int l, int r, int id = 1, int s = 0, int e = n) {
if (r <= s || e <= l) {
return 0;
}
if (l <= s && e <= r) {
return seg2[id];
}
int md = (s + e) / 2;
return max(get2(l, r, id * 2, s, md), get2(l, r, id * 2 + 1, md, e));
}
int getans() {
long long mp = 1;
long long ans = 0;
long long u = 1;
int mx = 0, mfor = 0;
long long mmp = 1;
set <int, greater <int> > :: iterator it = s.begin();
while (true) {
int k = *it;
if (k == -1) {
// ans = max(ans, get2(0, n));
break;
}
// cout << "75 " << k << endl;
int t = get2(k, n);
long long s = get1(0, k + 1);
u = s;
s *= t;
s %= mod;
// cout << "78 " << k << " " << t << " " << s << " " << mp << endl;
if (1ll * mp * mx < 1ll * mmp * t) {
mmp = mp;
mx = t;
mfor = k;
}
mp *= a[k];
if (mp > mod) {
break;
}
it++;
}
ans = get1(0, mfor + 1) * mx;
ans %= mod;
// cout << "74 " << mfor << " " << mx << " " << ans << endl;
return ans;
}
int32_t init(int nn, int X[], int Y[]) {
n = nn;
fill(seg1, seg1 + n * 4, 1);
for (int i = 0; i < n; i++) {
a[i] = X[i];
b[i] = Y[i];
update1(i, a[i]);
update2(i, b[i]);
if (a[i] > 1) {
s.insert(i);
}
}
s.insert(-1);
s.insert(0);
// cout << "72 " << get1(0, 3) << " " << get2(0, 3) << endl;
return getans();
}
int32_t updateX(int pos, int val) {
update1(pos, val);
if (val > 1) {
s.insert(pos);
}
else if(pos != 0) {
s.erase(pos);
}
a[pos] = val;
return getans();
}
int32_t updateY(int pos, int val) {
update2(pos, val);
a[pos] = val;
return getans();
}