#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "horse.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int mod = 1e9 + 7;
const int N = 5e5 + 10;
int n, st[N * 4];
int BIT[N];
int power(int a, int n) {
int ans = 1;
for (; n; n >>= 1)
if (n & 1) ans = 1LL * ans * a % mod;
return ans;
}
void add(int i, int mul) {
for (++i; i < N; i += i & - i) BIT[i] = 1LL * BIT[i] * mul % mod;
}
int get(int i) {
int ans = 1;
for (++i; i; i -= i & - i) ans = 1LL * ans * BIT[i] % mod;
return ans;
}
void add(int id, int L, int R, int i, int val) {
if (L == R) {
st[id] = val;
return;
}
int mid = L + R >> 1;
if (i <= mid) add(id * 2, L, mid, i, val);
else add(id * 2 + 1, mid + 1, R, i, val);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int get(int id, int L, int R, int u, int v) {
if (u > R || L > v) return -1;
if (u <= L && R <= v) return st[id];
int mid = L + R >> 1;
return max(get(id * 2, L, mid, u, v), get(id * 2 + 1, mid + 1, R, u, v));
}
set <int> s;
int x[N], y[N];
int solve() {
int cur = n;
long long mul = 1, p = 1;
int best = -1;
int i = -1;
while (1) {
int last = *(--s.lower_bound(cur));
if (last == -1) break;
int val = get(1, 0, n - 1, last, cur - 1);
if (best == -1 || 1LL * best * p < val) {
best = val;
i = last;
p = 1;
}
p *= x[last];
mul *= x[last];
cur = last;
if (mul > 1e9) break;
}
int j = (*(--s.end()) == i ? n : *s.upper_bound(i));
return 1LL * get(i) * get(1, 0, n - 1, i, j - 1) % mod;
}
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];
s.insert(-1);
for (int i = 0; i < n; ++i) if (x[i] != 1) s.insert(i);
for (int i = 0; i < n; ++i) BIT[i + 1] = 1;
for (int i = 0; i < n; ++i) add(i, x[i]);
for (int i = 0; i < n; ++i) add(1, 0, n - 1, i, y[i]);
return solve();
}
int updateX(int i, int val) {
if (x[i] != 1) s.erase(i);
add(i, power(x[i], mod - 2));
x[i] = val;
if (x[i] != 1) s.insert(i);
add(i, x[i]);
return solve();
}
int updateY(int i, int val) {
add(1, 0, n - 1, i, val);
return solve();
}
//
//
//int main() {
//// freopen("test.inp", "r", stdin);
// ios :: sync_with_stdio(0); cin.tie(0);
// int n, m;
// cin >> n;
// int x[n], y[n];
// for (int i = 0; i < n; ++i) cin >> x[i];
// for (int i = 0; i < n; ++i) cin >> y[i];
// cin >> m;
// cout << init(n, x, y) << '\n';
// while (m--) {
// int cmd, i, val;
// cin >> cmd >> i >> val;
// if (cmd == 1) cout << updateX(i, val) << '\n';
// else cout << updateY(i, val) << '\n';
// }
//}
Compilation message
horses.cpp:6:10: fatal error: horse.h: No such file or directory
6 | #include "horse.h"
| ^~~~~~~~~
compilation terminated.
