| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 240996 | ant101 | Horses (IOI15_horses) | C++14 | 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 <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
//#include "horses.h"
using namespace std;
typedef long long ll;
typedef long double ld;
const ld EPS = 1e-9;
const ll N = 5e5 + 10;
const ll MOD = 1e9 + 7;
ll n;
ll x[N], y[N];
ll tree[4 * N];
ld xlog[N], ylog[N];
ll product[N + N];
ld logsum[N + N];
void init_product (void) {
for (ll i = 0; i < n; ++i) {
product[n + i] = x[i] % MOD;
}
for (ll i = n - 1; i; --i) {
product[i] = (product[i << 1] * product[i << 1 | 1]) % MOD;
}
}
void modify_product (ll p, ll v) {
for (product[p += n] = v; p > 1; p >>= 1) {
product[p >> 1] = (product[p] * product[p ^ 1]) % MOD;
}
}
ll find_product (ll l, ll r) {
ll ret = 1LL;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ret *= product[l++], ret %= MOD;
if (r & 1) ret *= product[--r], ret %= MOD;
}
return ret;
}
void init_logsum (void) {
for (ll i = 0; i < n; ++i) {
logsum[n + i] = xlog[i];
}
for (ll i = n - 1; i; --i) {
logsum[i] = logsum[i << 1] + logsum[i << 1 | 1];
}
}
void modify_logsum (ll p, ld v) {
for (logsum[p += n] = v; p > 1; p >>= 1) {
logsum[p >> 1] = logsum[p] + logsum[p ^ 1];
}
}
ld find_logsum (ll l, ll r) {
ld ret = 0.0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ret += logsum[l++];
if (r & 1) ret += logsum[--r];
}
return ret;
}
ll merged (ll p, ll q) {
if (p > q) {
swap(p, q);
}
return (find_logsum(p + 1, q + 1) - ylog[p] + ylog[q] > -EPS) ? q : p;
}
void init_tree(ll u, ll b, ll e) {
if (b == e) {
tree[u] = b;
return;
}
ll l = u << 1;
ll r = l | 1;
ll m = b + e >> 1;
init_tree(l, b, m);
init_tree(r, m + 1, e);
tree[u] = merged(tree[l], tree[r]);
}
void modify_tree(ll u, ll b, ll e, ll p) {
if (b > p || e < p) return;
if (b == e) return;
ll l = u << 1;
ll r = l | 1;
ll m = b + e >> 1;
modify_tree(l, b, m, p);
modify_tree(r, m + 1, e, p);
tree[u] = merged(tree[l], tree[r]);
}
ll value(ll index) {
return (find_product(0, index + 1) * y[index]) % MOD;
}
ll init(ll N, ll X[], ll Y[]) {
n = N;
for (ll i = 0; i < n; i++) {
x[i] = X[i];
y[i] = Y[i];
xlog[i] = log(x[i]);
ylog[i] = log(y[i]);
}
init_product();
init_logsum();
init_tree(1, 0, n - 1);
return value(tree[1]);
}
ll updateX(ll pos, ll val) {
x[pos] = val, xlog[pos] = log(val);
modify_product(pos, x[pos]);
modify_logsum(pos, xlog[pos]);
modify_tree(1, 0, n - 1, pos);
return value(tree[1]);
}
ll updateY(ll pos, ll val) {
y[pos] = val, ylog[pos] = log(val);
modify_tree(1, 0, n-1, pos);
return value(tree[1]);
}
int main() {
return 0;
}