| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1328037 | edo | 말 (IOI15_horses) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "horses.h"
const int nax = 524288;
const int md = 1e9 + 7;
using ld = long double;
int n;
struct Node {
ld logX;
ld mxlog;
ll prodX;
ll best;
};
int curX[nax];
int curY[nax];
Node tree[nax << 1];
Node merge(const Node& L, const Node& R) {
Node res;
res.logX = L.logX + R.logX;
res.prodX = (L.prodX * R.prodX) % md;
if(L.mxlog >= L.logX + R.mxlog) {
res.mxlog = L.mxlog;
res.best = L.best;
}
else {
res.mxlog = L.logX + R.mxlog;
res.best = (L.prodX * R.best) % md;
}
return res;
}
void upd(int i) {
int p = i + nax;
tree[p].logX = log((ld)curX[i]);
tree[p].mxlog = tree[p].logX + log((ld)curY[i]);
tree[p].prodX = curX[i];
tree[p].best = (1LL * curX[i] * curY[i]) % md;
for(p >>= 1; p; p >>= 1) {
tree[p] = merge(tree[p << 1], tree[p << 1 | 1]);
}
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i = 0; i < nax; i++) {
if(i < n) {
curX[i] = X[i];
curY[i] = Y[i];
}
else
curX[i] = curY = 1;
}
for(int i = 0; i < nax; i++) {
int p = nax + i;
tree[p].logX = log((ld)curX[i]);
ld valY = (i < n) ? log((ld)curY[i]) : -1e18;
tree[p].mxlog = tree[p].logX + valY;
tree[p].prodX = curX[i];
tree[p].best = (1LL * curX[i] * curY[i]) % md;
}
for(int i = nax - 1; i > 0; i--) {
tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
}
return (int)tree[1].best;
}
int updateX(int pos, int val) {
curX[pos] = val;
upd(pos);
return (int)tree[1].best;
}
int updateY(int pos, int val) {
curY[pos] = val;
upd(pos);
return (int)tree[1].best;
}
