#include "horses.h" #include <bits/stdc++.h> #pragma GCC Optimize("O3") #define FOR(i, x, y) for (int i = x; i < y; i++) #define MOD 1000000007 typedef long long ll; using namespace std; ll expo(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res = (res * a) % MOD; a = (a * a) % MOD; b >>= 1; } return res; } const int MAXN = 500001; int n, X[MAXN], Y[MAXN]; double pref_logs[MAXN]; pair<double, int> mx[4 * MAXN]; double lazy_mx[4 * MAXN]; ll prods[4 * MAXN]; ll lazy_prod[4 * MAXN]; void push_lazy_mx(int l, int r, int node) { mx[node].first += lazy_mx[node]; if (l != r) { lazy_mx[node * 2] += lazy_mx[node]; lazy_mx[node * 2 + 1] += lazy_mx[node]; } lazy_mx[node] = 0; } void push_lazy_prod(int l, int r, int node) { prods[node] = (prods[node] * lazy_prod[node]) % MOD; if (l != r) { lazy_prod[node * 2] = (lazy_prod[node * 2] * lazy_prod[node]) % MOD; lazy_prod[node * 2 + 1] += (lazy_prod[node * 2 + 1] * lazy_prod[node]) % MOD; } lazy_prod[node] = 0; } void build(int l = 1, int r = n, int node = 1) { if (l == r) { mx[node] = {pref_logs[l] + log(Y[l]), l}; prods[node] = X[l]; } else { int mid = (l + r) / 2; build(l, mid, node * 2); build(mid + 1, r, node * 2 + 1); mx[node] = max(mx[node * 2], mx[node * 2 + 1]); prods[node] = (prods[node * 2] * prods[node * 2 + 1]) % MOD; } } void update_mx(int a, int b, double val, int l = 1, int r = n, int node = 1) { if (lazy_mx[node] != 0) push_lazy_mx(l, r, node); if (l > b || r < a) return; if (l >= a && r <= b) { lazy_mx[node] = val; push_lazy_mx(l, r, node); } else { int mid = (l + r) / 2; update_mx(a, b, val, l, mid, node * 2); update_mx(a, b, val, mid + 1, r, node * 2 + 1); mx[node] = max(mx[node * 2], mx[node * 2 + 1]); } } void update_prod(int pos, ll val, int l = 1, int r = n, int node = 1) { if (lazy_prod[node]) push_lazy_prod(l, r, node); if (l > pos) return; if (r <= pos) { lazy_prod[node] = val; push_lazy_prod(l, r, node); } else { int mid = (l + r) / 2; update_prod(pos, val, l, mid, node * 2); update_prod(pos, val, mid + 1, r, node * 2 + 1); prods[node] = (prods[node * 2] * prods[node * 2 + 1]) % MOD; } } int query_mx() { return mx[1].second; } ll query_prod(int pos, int l = 1, int r = n, int node = 1) { if (lazy_prod[node]) push_lazy_prod(l, r, node); if (l > pos) return 1; if (r <= pos) return prods[node]; int mid = (l + r) / 2; return (query_prod(pos, l, mid, node * 2) * query_prod(pos, mid + 1, r, node * 2 + 1)) % MOD; } int init(int N, int X[], int Y[]) { n = N; FOR(i, 0, n) ::X[i + 1] = X[i], ::Y[i + 1] = Y[i]; FOR(i, 1, n + 1) pref_logs[i] = pref_logs[i - 1] + log(::X[i]); build(); int best = query_mx(); return (int)((query_prod(best) * Y[best]) % MOD); } int updateX(int pos, int val) { pos++; double mx_up = log(val) - log(X[pos]); ll prod_up = (expo(X[pos], MOD - 2) * val) % MOD; X[pos] = val; update_mx(1, pos, mx_up); update_prod(pos, prod_up); int best = query_mx(); return (int)((query_prod(best) * Y[best]) % MOD); } int updateY(int pos, int val) { pos++; double mx_up = log(val) - log(Y[pos]); Y[pos] = val; update_mx(pos, pos, mx_up); int best = query_mx(); return (int)((query_prod(best) * Y[best]) % MOD); }

horses.cpp:3:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")
 
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:101:33: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:22:17: note: shadowed declaration is here
 int n, X[MAXN], Y[MAXN];
                 ^
horses.cpp:101:33: warning: declaration of 'X' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:22:8: note: shadowed declaration is here
 int n, X[MAXN], Y[MAXN];
        ^