# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1190976 | pensive | Robots (IOI13_robots) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define REP(a,i,n) for (ll i=a;i<n;i++)
#define ll long long
#define ssize 500'005
#define ld long double
const ll MOD = 1e9+7;
int N;
ll eks[ssize];
ll X[ssize], Y[ssize];
ll bin_exp(ll a, ll b) {
if (b == 0) return 1;
if (b % 2) return (bin_exp(a, b - 1) * a) % MOD;
ll res = bin_exp(a, b >> 1);
return (res * res) % MOD;
}
ll inv(ll a) {
return bin_exp(a, MOD - 2);
}
struct SegTree{
ll l, r, real, rLazy;
SegTree *lt, *rt;
ld lazy, val;
void combine(){
if (lt->val > rt->val) {
val = lt->val;
real = lt->real;
return;
}
val = rt->val;
real = rt->real;
}
SegTree(ll left, ll right, ll X[], vector<ld> &a){
l = left;
r = right;
lt = rt = nullptr;
lazy = 0, rLazy = 1;
if(left == right){
val = a[left];
real = X[left];
return;
}
ll mid = (l+r)>>1;
lt = new SegTree(l, mid, X, a);
rt = new SegTree(mid+1,r, X, a);
combine();
}
void propagate(){
if(lazy || rLazy!=1){
val += lazy;
real = (real*rLazy)%MOD;
if(lt) {
lt->lazy += lazy;
lt->rLazy = (lt->rLazy*rLazy)%MOD;
}
if(rt) {
rt->lazy += lazy;
rt->rLazy = (rt->rLazy*rLazy)%MOD;
}
}
lazy = 0;
rLazy = 1;
}
void update(ll ul, ll ur, ll newX, ld logged){
propagate();
if(ul > r || ur < l){
return;
}
if(ul <= l && r <= ur){
lazy += logged;
rLazy = (rLazy*newX)%MOD;
propagate();
return;
}
lt->update(ul,ur,newX, logged);
rt->update(ul,ur,newX, logged);
combine();
}
pair<ld, ll> query(ll ql, ll qr){
propagate();
if(ql > r || qr < l){
return {-MOD, 0};
}
if(ql <= l && r <= qr){
return {val, real};
}
return max(lt->query(ql,qr), rt->query(ql,qr));
}
ld solve() {
pair<ld, ll> pa = query(0, N-1);
return pa.second;
}
};
SegTree *st;
ll init(int n, int x[], int y[]) {
N = n;
REP(0,i,n) {
X[i] = x[i]; Y[i] = y[i];
}
vector<ld> a(1, log10(x[0]));
eks[0] = x[0];
REP(1,i,n) {
a.push_back(a.back()+log10(X[i])); //prefsum of log10 x
eks[i] = (eks[i-1]*X[i])%MOD;
}
REP(0, i, n) {
eks[i] = (eks[i]*Y[i])%MOD;
a[i] += log10(Y[i]);
}
st = new SegTree(0, N-1, eks, a); //a is log10 version of eks. its pref sum + y values
return st->solve();
}
ll updateX(int pos, int val) {
ll v = val;
st->update(pos, N-1, inv(X[pos]), -log10(X[pos])); // remove old value
st->update(pos, N-1, v, log10(v)); // new val
X[pos] = v; // mark new val
return st->solve();
}
ll updateY(int pos, int val) {
ll v = val;
st->update(pos, pos, inv(Y[pos]), -log10(Y[pos]));
st->update(pos, pos, v, log10(v));
Y[pos] = v;
return st->solve();
}