| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1277500 | k12_khoi | Horses (IOI15_horses) | C++17 | 0 ms | 0 KiB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define X first
#define Y second
const int N = 500000 + 5;
const int mod = 1000000007;
const int limit = 1000000000;
int n, request, type, x, y;
int a[N], b[N], Xarr[N], Yarr[N];
int t[4 * N], lazy[4 * N], tTwo[4 * N];
set<int> se;
set<int>::iterator it;
int mul(int x, int y) {
return int((1LL * x * y) % mod);
}
int luythua(int x, int n) {
int c = 1;
while (n) {
if (n & 1) c = mul(c, x);
x = mul(x, x);
n >>= 1;
}
return c;
}
void down(int id) {
if (lazy[id] != 1) {
// propagate lazy multiplication to children for tTwo
lazy[id << 1] = mul(lazy[id << 1], lazy[id]);
lazy[id << 1 | 1] = mul(lazy[id << 1 | 1], lazy[id]);
tTwo[id << 1] = mul(tTwo[id << 1], lazy[id]);
tTwo[id << 1 | 1] = mul(tTwo[id << 1 | 1], lazy[id]);
lazy[id] = 1;
}
}
void build_tree(int id, int l, int r, const vector<int> &pref_mod) {
lazy[id] = 1;
tTwo[id] = 1;
if (l == r) {
if (l == 0) t[id] = 1;
else t[id] = Yarr[l - 1];
// tTwo at leaf l is prefix_mod[l]
tTwo[id] = pref_mod[l];
return;
}
int m = (l + r) >> 1;
build_tree(id << 1, l, m, pref_mod);
build_tree(id << 1 | 1, m + 1, r, pref_mod);
t[id] = max(t[id << 1], t[id << 1 | 1]);
}
void update_range(int id, int l, int r, int u, int v, int k) {
if (u > r || v < l) return;
if (u <= l && r <= v) {
tTwo[id] = mul(tTwo[id], k);
lazy[id] = mul(lazy[id], k);
return;
}
down(id);
int m = (l + r) >> 1;
update_range(id << 1, l, m, u, v, k);
update_range(id << 1 | 1, m + 1, r, u, v, k);
}
void update_point(int id, int l, int r, int pos, int val) {
if (l == r) {
t[id] = val;
return;
}
int m = (l + r) >> 1;
if (pos <= m) update_point(id << 1, l, m, pos, val);
else update_point(id << 1 | 1, m + 1, r, pos, val);
t[id] = max(t[id << 1], t[id << 1 | 1]);
}
int get_range(int id, int l, int r, int u, int v) {
if (u > r || v < l) return 0;
if (u <= l && r <= v) return t[id];
down(id);
int m = (l + r) >> 1;
return max(get_range(id << 1, l, m, u, v), get_range(id << 1 | 1, m + 1, r, u, v));
}
int get_point(int id, int l, int r, int pos) {
if (l == r) return tTwo[id];
down(id);
int m = (l + r) >> 1;
if (pos <= m) return get_point(id << 1, l, m, pos);
else return get_point(id << 1 | 1, m + 1, r, pos);
}
int init_func(int nn, int aarr[], int barr[]) {
n = nn;
for (int i = 0; i < n; ++i) {
Xarr[i] = aarr[i];
Yarr[i] = barr[i];
}
// prepare prefix modulo array
vector<int> pref_mod(n + 1);
pref_mod[0] = 1;
for (int i = 1; i <= n; ++i) pref_mod[i] = mul(pref_mod[i - 1], Xarr[i - 1]);
// init segment tree arrays
int SZ = 4 * (n + 5);
for (int i = 0; i < SZ; ++i) {
t[i] = 0;
lazy[i] = 1;
tTwo[i] = 1;
}
// insert set indices
se.clear();
se.insert(0);
for (int i = 0; i < n; ++i) if (Xarr[i] != 1) se.insert(i + 1);
// build tree
build_tree(1, 0, n, pref_mod);
// find best according to your described iteration (multiply old then --it then check pos)
it = prev(se.end());
int best = *it;
// init ma as (maxY at last pos, 1)
int u = *it, v = n;
pii ma = make_pair(get_range(1, 0, n, u, v), 1);
long long cur = 1;
while (it != se.begin()) {
int old = *it;
if (old) {
cur = cur * 1LL * Xarr[old - 1];
if (cur >= limit) cur = limit;
}
--it;
int pos = *it;
u = pos; v = n;
int temp = get_range(1, 0, n, u, v);
if ((long long)ma.first * cur < (long long)temp * ma.second) {
best = pos;
ma.first = temp;
ma.second = 1; // keep behavior you wanted
cur = 1;
}
}
// result = prefix(best) * maxY(best..n) mod
int prefMod = get_point(1, 0, n, best);
int maxY = get_range(1, 0, n, best, n);
return mul(prefMod, maxY);
}
int updateX_func(int pos0, int val) {
int pos = pos0 + 1; // internal indexing
if (Xarr[pos - 1] != val) {
if (Xarr[pos - 1] == 1) se.insert(pos);
int k = mul(luythua(Xarr[pos - 1], mod - 2), val);
update_range(1, 0, n, pos, n, k); // multiply prefix [pos..n] by k (mod)
Xarr[pos - 1] = val;
if (val == 1) se.erase(pos);
}
// find best (same as init)
it = prev(se.end());
int best = *it;
int u = *it, v = n;
pii ma = make_pair(get_range(1, 0, n, u, v), 1);
long long cur = 1;
while (it != se.begin()) {
int old = *it;
if (old) {
cur = cur * 1LL * Xarr[old - 1];
if (cur >= limit) cur = limit;
}
--it;
int pos2 = *it;
u = pos2; v = n;
int temp = get_range(1, 0, n, u, v);
if ((long long)ma.first * cur < (long long)temp * ma.second) {
best = pos2;
ma.first = temp;
ma.second = 1;
cur = 1;
}
}
int prefMod = get_point(1, 0, n, best);
int maxY = get_range(1, 0, n, best, n);
return mul(prefMod, maxY);
}
int updateY_func(int pos0, int val) {
int pos = pos0 + 1;
if (Yarr[pos - 1] != val) {
// update point at pos (Y value stored at leaf index pos)
update_point(1, 0, n, pos, val);
Yarr[pos - 1] = val;
}
// find best (same as init)
it = prev(se.end());
int best = *it;
int u = *it, v = n;
pii ma = make_pair(get_range(1, 0, n, u, v), 1);
long long cur = 1;
while (it != se.begin()) {
int old = *it;
if (old) {
cur = cur * 1LL * Xarr[old - 1];
if (cur >= limit) cur = limit;
}
--it;
int pos2 = *it;
u = pos2; v = n;
int temp = get_range(1, 0, n, u, v);
if ((long long)ma.first * cur < (long long)temp * ma.second) {
best = pos2;
ma.first = temp;
ma.second = 1;
cur = 1;
}
}
int prefMod = get_point(1, 0, n, best);
int maxY = get_range(1, 0, n, best, n);
return mul(prefMod, maxY);
}