#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; const int MAXN = 500001; int n, x[MAXN], y[MAXN]; double pref_log2s[MAXN]; pair<double, int> mx[4 * MAXN]; double lazy_mx[4 * MAXN]; ll prods[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 build(int l = 1, int r = n, int node = 1) { if (l == r) { mx[node] = {pref_log2s[l] + log2(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 (l == r) prods[node] = val; else { int mid = (l + r) / 2; if (pos > mid) update_prod(pos, val, mid + 1, r, node * 2 + 1); else update_prod(pos, val, l, mid, node * 2); 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 (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_log2s[i] = pref_log2s[i - 1] + log2(x[i]); build(); int best = query_mx(); return (query_prod(best) * y[best]) % MOD; } int updateX(int pos, int val) { pos++; double mx_up = log2(val) - log2(x[pos]); x[pos] = val; update_mx(1, pos, mx_up); update_prod(pos, val); int best = query_mx(); return (query_prod(best) * y[best]) % MOD; } int updateY(int pos, int val) { pos++; double mx_up = log2(val) - log2(y[pos]); y[pos] = val; update_mx(pos, pos, mx_up); int best = query_mx(); return (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:82:38: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (query_prod(best) * y[best]) % MOD;
                                      ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:96:38: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (query_prod(best) * y[best]) % MOD;
                                      ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:109:38: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (query_prod(best) * y[best]) % MOD;
                                      ^