| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 65894 | daniel_02 | Horses (IOI15_horses) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "horses.h"
#include "bits/stdc++.h"
#define ll long long
#define fr first
#define sc second
using namespace std;
const int MOD = 1e9 + 7;
const int sz = 5e5 + 7;
ll n, x[sz], y[sz];
pair<double, ll> t[sz * 6], ad[sz * 6], an[sz];
pair<double, ll> maxp(pair<double, ll> a, pair<double, ll> b)
{
if (a.fr > b.fr)
{
return a;
}
else
{
return b;
}
}
ll bin_pow(ll a, ll n)
{
if (n == 1)return a;
if (n & 1)
return ((a * 1LL * bin_pow(a, n - 1)) % MOD);
else
{
ll b = bin_pow(a, n / 2);
return ((b * b) % MOD);
}
}
void build(int v, int tl, int tr)
{
if (tl == tr)
{
t[v].fr = an[tl].fr;
t[v].sc = an[tl].sc;
}
else
{
int mid = (tl + tr) >> 1;
build(v + v, tl, mid);
build(v + v + 1, mid + 1, tr);
t[v] = maxp(t[v + v], t[v + v + 1]);
}
}
void push(int v, int tl, int tr)
{
if (ad[v].sc == -1)return;
t[v].fr += ad[v].fr;
t[v].sc = (ad[v].sc * t[v].sc) % MOD;
ad[v + v].fr += ad[v].fr;
ad[v + v + 1].fr += ad[v].fr;
ad[v + v].sc = (ad[v].sc * ad[v + v].sc) % MOD;
ad[v + v + 1].sc = (ad[v].sc * ad[v + v + 1].sc) % MOD;
ad[v].fr = 0;
ad[v].sc = -1;
}
void updy(int v, int tl, int tr, int pos, double val, ll val1)
{
push(v, tl, tr);
if (tl == tr)
{
t[v].fr += val;
t[v].sc = (t[v].sc * val1) % MOD;
}
else
{
int mid = (tl + tr) >> 1;
if (mid >= pos)
updy(v + v, tl, mid, pos, val, val1);
else
updy(v + v + 1, mid + 1, tr, pos, val, val1);
t[v] = maxp(t[v + v], t[v + v + 1]);
push(v, tl, tr);
}
}
void updx(int v, int tl, int tr, int l, int r, double val, ll val1)
{
push(v, tl, tr);
if (tl > r || l > tr)return;
if (l <= tl && tr <= r)
{
ad[v].fr += val;
if (ad[v].sc == -1)ad[v].sc = 1;
ad[v].sc = (val1 * 1LL * ad[v].sc) % MOD;
push(v, tl, tr);
}
else
{
int mid = (tl + tr) >> 1;
updx(v + v, tl, mid, l, r, val, val1);
updx(v + v + 1, mid + 1, tr, l, r, val, val1);
push(v, tl, tr);
t[v] = maxp(t[v + v], t[v + v + 1]);
}
}
void get(int v, int tl, int tr, int pos)
{
push(v, tl, tr);
if (tl == tr)
{
cout << t[v].fr << " " << t[v].sc << endl;
}
else
{
int mid = (tl + tr) >> 1;
if (mid >= pos)
get(v + v, tl, mid, pos);
else
get(v + v + 1, mid + 1, tr, pos);
push(v, tl, tr);
t[v] = maxp(t[v + v], t[v + v + 1]);
}
}
int init(int N, int X[], int Y[]) {
double h = 0;
ll cur = 1;
double ans = 0;
ll ans1 = 1;
n = N;
for (int i = 0; i < sz * 6 - 1; i++)
{
ad[i].sc = -1;
}
for (int i = 0; i < N; i++)
{
x[i + 1] = X[i];
y[i + 1] = Y[i];
}
for (int i = 0; i < N; i++)
{
h += log10(X[i]);
cur = (cur * X[i]) % MOD;
an[i + 1] = {h + log10(Y[i]), (cur * 1LL * Y[i]) % MOD};
if (ans * 1.0 < h + log10(Y[i]))
{
ans = log10(Y[i]) + h;
ans1 = (Y[i] * 1LL * cur) % MOD;
}
}
build(1, 1, n);
return (ans1 % MOD);
}
int updateX(ll pos, ll val) {
pos++;
double a = (log10(val) - log10(x[pos]));
ll b = (val * bin_pow(x[pos], MOD - 2)) % MOD;
updx(1, 1, n, pos, n, a, b);
x[pos] = val;
return (t[1].sc % MOD);
}
int updateY(ll pos, ll val) {
pos++;
double a = log10(val) - log10(y[pos]);
ll b = (val * bin_pow(y[pos], MOD - 2)) % MOD;
updy(1, 1, n, pos, a, b);
y[pos] = val;
return (t[1].sc % MOD);
}