#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
const int mod = 1e9 + 7;
int n, x[MAXN], y[MAXN];
int prodx[MAXN];
double lgx[MAXN];
int binpow(int a, int b) {
int ret = 1;
while(b) {
if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod;
b >>= 1;
}
return ret;
}
int inverse(int a) {
return binpow(a, mod - 2);
}
struct SegmentTree {
pair <double, int> t[MAXN << 2];
pair <double, int> lz[MAXN << 2];
#define mid ((l + r) >> 1)
void build(int v, int l, int r) {
lz[v] = {0.0, 1};
if (l == r) {
t[v] = {lgx[l] + (double)log(y[l]), 1LL * prodx[l] * y[l] % mod};
return;
}
build(v << 1, l, mid);
build(v << 1 | 1, mid + 1, r);
t[v] = max(t[v << 1], t[v << 1 | 1]);
}
void merge(pair<double, int> &p, pair<double, int> q) {
p.first += q.first;
p.second = 1LL * p.second * q.second % mod;
}
void push(int v, int l, int r) {
if (lz[v].second == 1) return;
if (l < r) merge(lz[v << 1], lz[v]), merge(lz[v << 1 | 1], lz[v]);
t[v].first += lz[v].first; // log
t[v].second = 1LL * t[v].second * lz[v].second % mod;
}
void upd(int v, int l, int r, int L, int R, int mul, double lg) {
push(v, l, r);
if (R < l || L > r) return;
if (L <= l && r <= R) {
lz[v] = {lg, mul}; push(v, l, r); return;
}
upd(v << 1, l, mid, L, R, mul, lg);
upd(v << 1 | 1, mid + 1, r, L, R, mul, lg);
t[v] = max(t[v << 1], t[v << 1 | 1]);
}
} seg;
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 0; i < n; ++i) {
x[i] = X[i];
y[i] = Y[i];
}
prodx[0] = x[0];
lgx[0] = log(x[0]);
for (int i = 1; i < n; ++i) {
prodx[i] = 1LL * prodx[i - 1] * x[i] % mod;
lgx[i] = lgx[i - 1] + log(x[i]);
}
seg.build(1, 0, n - 1);
return seg.t[1].second;
}
int updateX(int pos, int val) {
seg.upd(1, 0, n - 1, pos, n - 1, inverse(x[pos]), -log(x[pos]));
seg.upd(1, 0, n - 1, pos, n - 1, val, log(val));
x[pos] = val;
return seg.t[1].second;
}
int updateY(int pos, int val) {
seg.upd(1, 0, n - 1, pos, pos, inverse(y[pos]), -log(y[pos]));
seg.upd(1, 0, n - 1, pos, pos, val, log(val));
y[pos] = val;
return seg.t[1].second;
}
Compilation message
Compilation timeout while compiling horses
