| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 726495 | becaido | Horses (IOI15_horses) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define lpos pos*2
#define rpos pos*2+1
const int MOD = 1e9 + 7;
const int SIZE = 5e5 + 5;
struct Node {
int pro = 1;
long double sum = 0, mx = 0;
Node operator + (const Node& rhs) const {
Node re;
re.pro = 1ll * pro * rhs.pro % MOD;
re.sum = sum + rhs.sum;
re.mx = max(mx, sum + rhs.mx);
return re;
}
} node[4 * SIZE];
int n, y[SIZE];
void upd(int pos, int l, int r, int p, int ty, int x) {
if (l == r) {
if (ty == 1) {
node[pos].pro = x;
node[pos].sum = log((long double) x);
}
if (ty == 2) {
node[pos].mx = node[pos].sum + log((long double) (y[p] = x));
}
return;
}
int mid = (l + r) / 2;
if (p <= mid) upd(lpos, l, mid, p, ty, x);
else upd(rpos, mid + 1, r, p, ty, x);
node[pos] = node[lpos] + node[rpos];
}
int que(int pos, int l, int r, int cur = 1) {
if (l == r) return 1ll * cur * node[pos].pro % MOD * y[l] % MOD;
int mid = (l + r) / 2;
if (node[lpos].mx >= node[lpos].sum + node[rpos].mx) return que(lpos, l, mid, cur);
else return que(rpos, mid + 1, r, 1ll * cur * node[lpos].pro % MOD);
}
int init(int N, int X[], int Y[]) {
auto build = [&](auto build, int pos, int l, int r)->void {
if (l == r) {
node[pos].pro = X[l];
node[pos].sum = log((long double) X[l]);
node[pos].mx = node[pos].sum + log((long double) (y[l] = Y[l]));
return;
}
int mid = (l + r) / 2;
build(build, lpos, l, mid);
build(build, rpos, mid + 1, r);
node[pos] = node[lpos] + node[rpos];
};
n = N;
build(build, 1, 0, n - 1);
return que(1, 0, n - 1);
}
int updateX(int pos, int val) {
upd(1, 0, n - 1, pos, 1, val);
return que(1, 0, n - 1);
}
int updateY(int pos, int val) {
upd(1, 0, n - 1, pos, 2, val);
return que(1, 0, n - 1);
}