#include <bits/stdc++.h>
#include "horse.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T& container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
const int MOD = 1e9 + 7, N = 5e5 + 69;
int n;
vector<int> X, Y;
struct SegmentTreeProd{
int n;
vector<ll> a;
SegmentTreeProd(int _n){
n = _n;
a.resize(n * 2 + 2, 1);
}
void update(int i, int v){
i += n; a[i] = v;
while(i > 1){
i >>= 1;
a[i] = a[i * 2] * a[i * 2 + 1] % MOD;
}
}
ll get(int l, int r){
l += n; r += n + 1;
ll ans =1;
while(l < r){
if (l & 1) ans = ans * a[l++] % MOD;
if (r & 1) ans = ans * a[--r] % MOD;
l >>= 1; r >>= 1;
}
return ans;
}
};
struct SegmentTreeMax{
int n;
vector<int> a;
SegmentTreeMax(int _n){
n = _n;
a.resize(n * 2 + 2, 0);
}
void update(int i, int v){
i += n; a[i] = v;
while(i > 1){
i >>= 1;
a[i] = max(a[i * 2], a[i * 2 + 1]);
}
}
ll get(int l, int r){
l += n; r += n + 1;
int ans = 0;
while(l < r){
if (l & 1) maximize(ans, a[l++]);
if (r & 1) maximize(ans, a[--r]);
l >>= 1; r >>= 1;
}
return ans;
}
};
SegmentTreeProd st1(N);
SegmentTreeMax st2(N);
set<int> S;
int calc(){
if (S.size() == 0) return st2.get(1, n);
ll mul = 1;
auto it = S.end(); it--;
vector<pair<int, int>> chode;
while(true){
chode.push_back({*it, X[*it]});
mul *= chode.back().second;
if (mul > 1e9){
break;
}
else if (it == S.begin()) {
if (chode.back().first != 1) chode.push_back({1, 1});
break;
}
it--;
}
ll sugma = st1.get(1, chode.back().first - 1);
reverse(ALL(chode));
mul = 1;
for(pair<int, int> i: chode){
maximize(mul, 1LL * i.second * st2.get(i.first, n));
}
return sugma * mul % MOD;
}
int init(int _n, int x[], int y[]) {
n = _n;
X.resize(n+1); Y.resize(n+1);
for(int i = 0; i<n; ++i) X[i+1] = x[i];
for(int i = 0; i<n; ++i) Y[i+1] = y[i];
for(int i= 1; i<=n; ++i) st1.update(i, X[i]);
for(int i= 1; i<=n; ++i) st2.update(i, Y[i]);
for(int i = 1; i<=n; ++i) if (X[i] > 1) S.insert(i);
return calc();
}
int updateX(int pos, int val) {
pos++;
if (X[pos] > 1){
S.erase(pos);
}
X[pos] = val;
if (X[pos] > 1) S.insert(pos);
st1.update(pos, val);
return calc();
}
int updateY(int pos, int val) {
pos++;
st2.update(pos, val);
Y[pos] = val;
return calc();
}
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int x[] = {2, 1, 3}, y[] = {3, 4, 1};
// cout << init(3, x, y) << "\n";
// cout << updateY(1, 2) << "\n";
// return 0;
// }
Compilation message
horses.cpp:2:10: fatal error: horse.h: No such file or directory
2 | #include "horse.h"
| ^~~~~~~~~
compilation terminated.
