#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
const ll INF = 1e18;
const ld EPS = 1e-12;
#define endl "\n"
#define sp <<" "<<
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template <typename Key, typename Value>
using hash_map = unordered_map<Key, Value, custom_hash>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// uniform_int_distribution<int>(a, b)(rng);
// shuffle(all(a), rng);
int n;
vector<ll> x, y;
struct segtree {
int l, r;
double num, price;
ll modNum, modPrice;
segtree *left, *right;
void merge() {
num = left->num + right->num;
modNum = left->modNum * right->modNum;
modNum %= MOD;
if (left->price >= left->num + right->price) {
price = left->price;
modPrice = left->modPrice;
} else {
price = left->num + right->price;
modPrice = left->modNum * right->modPrice;
modPrice %= MOD;
}
}
segtree(int l, int r, vector<ll> &x, vector<ll> &y) : l(l), r(r) {
if (l == r) {
left = right = nullptr;
num = log10(x[l]), modNum = x[l];
price = num + log10(y[l]), modPrice = modNum * y[l], modPrice %= MOD;
return;
}
int m = (l+r)/2;
left = new segtree(l, m, x, y);
right = new segtree(m+1, r, x, y);
merge();
}
void update(int ind) {
if (l == r) {
num = log10(x[l]), modNum = x[l];
price = num + log10(y[l]), modPrice = modNum * y[l], modPrice %= MOD;
return;
}
int m = (l+r)/2;
if (ind <= m) left->update(ind);
else right->update(ind);
merge();
}
};
segtree *st;
int init(int N, int X[], int Y[]) {
n = N;
x.resize(n), y.resize(n);
REP(i, 0, n) {
x[i] = X[i];
y[i] = Y[i];
}
st = new segtree(0, n-1, x, y);
return st->modPrice;
}
int updateX(int pos, int val) {
x[pos] = val;
st->update(pos);
return st->modPrice;
}
int updateY(int pos, int val) {
y[pos] = val;
st->update(pos);
return st->modPrice;
}
// signed main() {
// int n; cin >> n;
// int x[n], y[n];
// REP(i, 0, n)
// cin >> x[i];
// REP(i, 0, n)
// cin >> y[i];
// cout << init(n, x, y) << endl;
// int q; cin >> q;
// while (q--) {
// int command; cin >> command;
// int ind, upd; cin >> ind >> upd;
// if (command == 1) {
// cout << updateX(ind, upd) << endl;
// } else {
// cout << updateY(ind, upd) << endl;
// }
// }
// 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... |