| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1186299 | jasonic | 말 (IOI15_horses) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
#define MOD 1000000007
struct ST{
double v, rv;
double bsY;
ll rprod, prod;
ll ans;
ll bsY_nolog;
ST *lt, *rt;
ll l, r;
/*
v: best range product in log 10
rv: full range product
bsY: the value of Y (in base 10) that maximizes answer
prod: best range product
rprod: full range product
ans: the answer for this range
bsY_nolog: i think u can understand that
*/
void combine() {
if(lt->v + lt->bsY > lt->rv + rt->v + rt->bsY) { // answer is better on the left
v = lt->v;
prod = lt->prod;
bsY = lt->bsY;
ans = lt->ans;
bsY_nolog = lt->bsY_nolog;
} else {
v = rt->v;
prod = (lt->rprod * rt->prod) % MOD;
bsY = rt->bsY;
ans = (lt->rprod * rt->ans) % MOD;
bsY_nolog = rt->bsY_nolog;
}
rv = lt->rv + rt->rv;
rprod = (lt->rprod * rt->rprod) % MOD;
}
ST(int bl, int br, int X[], int Y[]) {
lt = rt = nullptr;
v = rv = 0;
l = bl; r = br;
prod = rprod = 0;
bsY = -1;
ans = -1;
if(l == r) {
v = rv = X[l]==1?0:log10(X[l]);
prod = rprod = X[l];
bsY = Y[l]==1?0:log10(Y[l]);
bsY_nolog = Y[l];
ans = (X[l] * Y[l]) % MOD;
} else {
m = (l+r)>>1;
lt = new ST(l, m, X);
rt = new ST(m+1, r, X);
combine();
}
}
ll qryAns() {
return ans;
}
void updX(ll i, ll x) {
if(i < l || r < i) return;
if(l == r && r == i) {
v = rv = x==1?0:log10(x);
prod = rprod = x;
ans = x * bsY_nolog;
return;
}
lt->upd(i, x);
rt->upd(i, x);
combine();
}
void updY(ll i, ll y) {
if(i < l || r < i) return;
if(l == r && r == i) {
bsY = y==1?0:log10(y);
bsY_nolog = y;
ans = prod * y;
return;
}
lt->upd(i, y);
rt->upd(i, y);
combine();
}
};
ST tree;
ll init(int N, int X[], int Y[]) {
tree = ST(0, N-1, X, Y);
return tree.qryAns();
}
ll updateX(int i, int v) {
tree.updX(i, v);
return tree.qryAns();
}
ll updateY(int i, int v) {
tree.updY(i, v);
return tree.qryAns();
}