#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define count1 __builtin_popcount
#define all(v) v.begin(), v.end()
using namespace std;
struct point{
ll ans, sum;
double lg, anslg;
};
constexpr ll MAX = 5e+5 + 3, INF = 2e+9, MOD = 1e+9 + 7, K = log2(MAX);
ll n;
vector <ll> a, b;
vector <point> t(4 * MAX);
ll exp(ll a, ll b) {
if (b == 0) return 1;
if (b % 2) return (a * exp(a, b-1)) % MOD;
return exp((a*a)%MOD, b/2);
}
void build(ll v, ll tl, ll tr) {
if (tl == tr) {
t[v].ans = (a[tl] * b[tl]) % MOD;
t[v].sum = a[tl] % MOD;
t[v].lg = log10(a[tl]);
t[v].anslg = log10(t[v].ans);
return;
}
ll tm = (tl + tr) / 2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD;
if (t[v*2].anslg > t[v*2].lg + t[v*2+1].anslg) {
t[v].ans = t[v*2].ans;
t[v].anslg = t[v*2].anslg;
}
else {
t[v].ans = (t[v*2].sum * t[v*2+1].ans) % MOD;
t[v].anslg = t[v*2].lg + t[v*2+1].anslg;
}
t[v].lg = t[v*2].lg + t[v*2+1].lg;
}
void updatex(ll v, ll tl, ll tr, ll i, ll x) {
if (tl == tr) {
t[v].ans = (x * b[tl]) % MOD;
t[v].sum = x % MOD;
a[tl] = x;
return;
}
ll tm = (tl + tr) / 2;
if (i <= tm) {
updatex(v*2, tl, tm, i, x);
}
else {
updatex(v*2+1, tm+1, tr, i, x);
}
t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD;
if (t[v*2].anslg > t[v*2].lg + t[v*2+1].anslg) {
t[v].ans = t[v*2].ans;
t[v].anslg = t[v*2].anslg;
}
else {
t[v].ans = (t[v*2].sum * t[v*2+1].ans) % MOD;
t[v].anslg = t[v*2].lg + t[v*2+1].anslg;
}
t[v].lg = t[v*2].lg + t[v*2+1].lg;
}
void updatey(ll v, ll tl, ll tr, ll i, ll y) {
if (tl == tr) {
t[v].ans = (a[tl] * y) % MOD;
b[tl] = y;
return;
}
ll tm = (tl + tr) / 2;
if (i <= tm) {
updatey(v*2, tl, tm, i, y);
}
else {
updatey(v*2+1, tm+1, tr, i, y);
}
t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD;
if (t[v*2].anslg > t[v*2].lg + t[v*2+1].anslg) {
t[v].ans = t[v*2].ans;
t[v].anslg = t[v*2].anslg;
}
else {
t[v].ans = (t[v*2].sum * t[v*2+1].ans) % MOD;
t[v].anslg = t[v*2].lg + t[v*2+1].anslg;
}
t[v].lg = t[v*2].lg + t[v*2+1].lg;
}
int init(int N, int X[], int Y[]) {
cin >> N;
for (int i=0; i < N; i++) {
cin >> X[i];
}
for (int i=0; i < N; i++) {
cin >> Y[i];
}
n = (ll)N;
for (int i=0; i < N; i++) {
a.pb(X[i]);
b.pb(Y[i]);
}
build(1, 0, n-1);
return t[1].ans;
}
int updateX(int pos, int val) {
ll i = (ll)pos, x = (ll)val;
updatex(1, 0, n-1, i, x);
return t[1].ans;
}
int updateY(int pos, int val) {
ll i = (ll)pos, y = (ll)val;
updatey(1, 0, n-1, i, y);
return t[1].ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |