#include <bits/stdc++.h>
#include "horses.h"
// #define int long long
// #define double long double
#define fi first
#define se second
#define sz(a) (ll)((a).size())
#define aint(a) (a).begin(), (a).end()
#define lsb(x) (x & (-x))
#define vi vector<ll>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }
using ll = long long;
using ld = long double;
using pii = std::pair<ll, ll>;
const ll NMAX = 5e5;
const ll MOD = 1e9 + 7;
using namespace std;
ld sp[NMAX + 5];
ll X[NMAX + 5], Y[NMAX + 5], n;
inline ll modmul(ll a, ll b) {
return (__int128)a * b % MOD;
}
struct Seg {
ll aint[4 * NMAX + 5];
void build(ll nod = 1, ll st = 1, ll dr = n) {
if (st == dr) {
aint[nod] = X[st] % MOD;
return;
}
ll m = (st + dr) >> 1;
build(2 * nod, st, m);
build(2 * nod + 1, m + 1, dr);
aint[nod] = modmul(aint[2 * nod], aint[2 * nod + 1]);
}
void update(ll pos, ll val, ll nod = 1, ll st = 1, ll dr = n) {
if (st == dr) {
aint[nod] = val % MOD;
return;
}
ll m = (st + dr) >> 1;
if (pos <= m)
update(pos, val, 2 * nod, st, m);
else
update(pos, val, 2 * nod + 1, m + 1, dr);
aint[nod] = modmul(aint[2 * nod], aint[2 * nod + 1]);
}
ll query(ll l, ll r, ll nod = 1, ll st = 1, ll dr = n) {
if (st > r || dr < l) return 1;
if (l <= st && dr <= r) return aint[nod];
ll m = (st + dr) >> 1;
return modmul(query(l, r, 2 * nod, st, m), query(l, r, 2 * nod + 1, m + 1, dr));
}
}aint_prod;
struct Lazy_Seg {
struct Node {
ld val;
ll p;
Node() : val(numeric_limits<ld>::lowest()), p(0) {}
static Node merge(const Node& left, const Node& right) {
Node aux;
aux.val = max(left.val, right.val);
aux.p = (left.val > right.val ? left.p : right.p);
return aux;
}
};
Node aint[4 * NMAX + 5];
ld lazy[4 * NMAX + 5];
void build(ll nod = 1, ll st = 1, ll dr = n) {
if (st == dr) {
aint[nod].val = sp[st] + 1.0 * log10(Y[st]);
aint[nod].p = st;
return;
}
ll m = (st + dr) >> 1;
build(2 * nod, st, m);
build(2 * nod + 1, m + 1, dr);
aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
}
void push(ll nod, ll st, ll dr) {
if (lazy[nod] != 0) {
aint[nod].val += lazy[nod];
if (st != dr) {
lazy[2 * nod] += lazy[nod];
lazy[2 * nod + 1] += lazy[nod];
}
lazy[nod] = 0;
}
}
void update(ll pos, ld v, ll nod = 1, ll st = 1, ll dr = n) {
push(nod, st, dr);
if (st == dr) {
aint[nod].val += v;
return;
}
ll m = (st + dr) >> 1;
if (pos <= m)
update(pos, v, 2 * nod, st, m);
else
update(pos, v, 2 * nod + 1, m + 1, dr);
aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
}
void range_add(ll l, ll r, ld v, ll nod = 1, ll st = 1, ll dr = n) {
push(nod, st, dr);
if (st > r || dr < l) return;
if (l <= st && dr <= r) {
lazy[nod] += v;
push(nod, st, dr);
return;
}
ll m = (st + dr) >> 1;
range_add(l, r, v, 2 * nod, st, m);
range_add(l, r, v, 2 * nod + 1, m + 1, dr);
aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
}
Node query(ll l, ll r, ll nod = 1, ll st = 1, ll dr = n) {
push(nod, st, dr);
if (st > r || dr < l) return Node();
if (l <= st && dr <= r) return aint[nod];
ll m = (st + dr) >> 1;
return Node::merge(query(l, r, 2 * nod, st, m), query(l, r, 2 * nod + 1, m + 1, dr));
}
}aint;
int32_t init(int32_t n_, int32_t a[], int32_t b[]) {
n = n_;
copy(a, a + n, X + 1);
copy(b, b + n, Y + 1);
for (ll i = 1; i <= n; ++i)
sp[i] = sp[i - 1] + 1.0 * log10(X[i]);
aint.build();
aint_prod.build();
int p = aint.query(1, n).p;
return modmul(Y[p], aint_prod.query(1, p));
}
int32_t updateX(int32_t pos, int32_t val) {
ld dif = 1.0 * log10(val) - 1.0 * log10(X[pos]);
X[pos] = val;
aint.range_add(pos, n, dif);
aint_prod.update(pos, X[pos]);
int p = aint.query(1, n).p;
return modmul(Y[p], aint_prod.query(1, p));
}
int32_t updateY(int32_t pos, int32_t val) {
ld dif = 1.0 * log10(val) - 1.0 * log10(Y[pos]);
Y[pos] = val;
aint.update(pos, dif);
int p = aint.query(1, n).p;
return modmul(Y[p], aint_prod.query(1, p));
}
// signed main() {
// cin.tie(nullptr)->sync_with_stdio(false);
//
// ll N; cin >> N;
// vector<ll> a(N+1), b(N+1);
// for (ll i = 1; i <= N; ++i) cin >> a[i];
// for (ll i = 1; i <= N; ++i) cin >> b[i];
// ll M; cin >> M;
// cout << init(N, a.data(), b.data()) << "\n";
// while (M--) {
// ll t, pos, val; cin >> t >> pos >> val;
// if (t == 1) cout << updateX(pos, val) << "\n";
// else cout << updateY(pos, val) << "\n";
// }
//
// return 0;
// }
# | 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... |