| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 289985 | Berted | 팀들 (IOI15_teams) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <iostream>
#include <algorithm>
#include <utility>
#define ll long long
#define pii pair<ll, ll>
#define fst first
#define snd second
const int SZ = (1 << 20) + 5;
const ll MD = 1e9 + 7;
using namespace std;
int n;
ll x[500001], y[500001];
namespace segX
{
pii seg[SZ];
inline pii merge(const pii &L, const pii &R)
{
pii ret;
ret.fst = min(MD, L.fst * R.fst);
ret.snd = (L.snd * R.snd) % MD;
return ret;
}
void build(int idx, int L, int R)
{
seg[idx] = {1, 1};
if (L <= R)
{
if (L == R) {seg[idx] = {x[L], x[R]};}
else
{
int M = L + R >> 1;
build(idx << 1, L, M);
build(idx << 1 | 1, M + 1, R);
seg[idx] = merge(seg[idx << 1], seg[idx << 1 | 1]);
}
}
}
void update(int idx, int L, int R, int x, int v)
{
if (L <= R)
{
if (L == x && x == R) {seg[idx] = {v, v};}
else
{
int M = L + R >> 1;
if (x <= M) {update(idx << 1, L, M, x, v);}
else {update(idx << 1 | 1, M + 1, R, x, v);}
seg[idx] = merge(seg[idx << 1], seg[idx << 1 | 1]);
}
}
}
pii query(int idx, int L, int R, int l, int r)
{
l = max(L, l); r = min(R, r);
if (l <= r)
{
if (L == l && R == r) {return seg[idx];}
else
{
int M = L + R >> 1;
return merge(query(idx << 1, L, M, l, r), query(idx << 1 | 1, M + 1, R, l, r));
}
}
return {1, 1};
}
}
namespace segY
{
int seg[SZ];
inline int merge(const int &L, const int &R)
{
if (L == -1) {return R;}
if (R == -1) {return L;}
if (y[R] * segX::query(1, 0, n - 1, L + 1, R).fst >= y[L]) {return R;}
else {return L;}
}
void build(int idx, int L, int R)
{
seg[idx] = -1;
if (L <= R)
{
if (L == R) {seg[idx] = L;}
else
{
int M = L + R >> 1;
build(2 * idx, L, M);
build(2 * idx + 1, M + 1, R);
seg[idx] = merge(seg[2 * idx], seg[2 * idx + 1]);
}
}
}
void update(int idx, int L, int R, int x)
{
if (L < R)
{
int M = L + R >> 1;
if (x <= M) {update(2 * idx, L, M, x);}
else {update(2 * idx + 1, M + 1, R, x);}
seg[idx] = merge(seg[2 * idx], seg[2 * idx + 1]);
}
}
}
inline ll eval(int idx) {return y[idx] * segX::query(1, 0, n - 1, 0, idx).snd % MD;}
int init(int N, int X[], int Y[])
{
n = N;
for (int i = 0; i < n; i++) {x[i] = X[i]; y[i] = Y[i];}
segX::build(1, 0, n - 1);
segY::build(1, 0, n - 1);
return eval(segY::seg[1]);
}
int updateX(int pos, int val)
{
segX::update(1, 0, n - 1, pos, val);
segY::update(1, 0, n - 1, pos);
return eval(segY::seg[1]);
}
int updateY(int pos, int val)
{
y[pos] = val;
segY::update(1, 0, n - 1, pos);
return eval(segY::seg[1]);
}