#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 500005;
const int modl = 1e9+7;
ll fen[MAXN];
int dp[12][MAXN], X[MAXN], Y[MAXN], nArr;
#ifdef Nhoksocqt1
int init(int _N, int _X[], int _Y[]);
int updateX(int pos, int val);
int updateY(int pos, int val);
int _X[MAXN], _Y[MAXN];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("HORSES.inp", "r", stdin);
freopen("HORSES.out", "w", stdout);
int _N;
cin >> _N;
for (int i = 0; i < _N; ++i) {
cin >> _X[i];
_X[i] = Random(1, 1e9); cout << _X[i] << " \n"[i + 1 == _N];
}
for (int i = 0; i < _N; ++i) {
cin >> _Y[i];
_Y[i] = Random(1, 1e9); cout << _Y[i] << " \n"[i + 1 == _N];
}
cout << init(_N, _X, _Y) << '\n';
int Q;
cin >> Q;
while(Q--) {
int type, pos, val;
cin >> type >> pos >> val;
type = Random(0, 1), pos = Random(0, _N - 1), val = Random(1, 1e9); cout << type << ' ' << pos << ' ' << val << '\n';
if(type == 0) {
cout << updateX(pos, val) << '\n';
} else {
cout << updateY(pos, val) << '\n';
}
}
return 0;
}
#endif // Nhoksocqt1
ll powermod(ll a, int exponent) {
ll res(1);
while(exponent > 0) {
if(exponent & 1)
res = res * a % modl;
a = a * a % modl;
exponent >>= 1;
}
return res;
}
void modify(int i, int v) {
for (; i > 0; i -= i & -i)
fen[i] = fen[i] * v % modl;
}
int get(int i) {
ll res(1);
for (; i <= nArr; i += i & -i)
res = res * fen[i] % modl;
return res;
}
int getx(int i) {
ll res(1);
for (; i <= nArr; i += i & -i)
res = min(ll(1e9)+1, res * fen[i]);
return res;
}
int query(int u, int v) {
return 1LL * get(u) * powermod(get(v + 1), modl - 2) % modl;
}
int segx[4 * MAXN], segy[4 * MAXN];
void build(int seg[], int id, int l, int r, int x[]) {
if(l == r) {
seg[id] = x[l];
return;
}
int mid = (l + r) >> 1;
build(seg, id << 1, l, mid, x);
build(seg, id << 1 | 1, mid + 1, r, x);
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
void update(int seg[], int pos, int val) {
int id(1), l(1), r(nArr);
while(l != r) {
int mid = (l + r) >> 1;
if(pos <= mid) {
id = id << 1;
r = mid;
} else {
id = id << 1 | 1;
l = mid + 1;
}
}
seg[id] = val;
while(id > 1) {
id >>= 1;
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
}
int query(int seg[], int id, int l, int r, int u, int v) {
if(u <= l && r <= v)
return seg[id];
int mid = (l + r) >> 1, res(0);
if(mid >= u)
res = max(res, query(seg, id << 1, l, mid, u, v));
if(mid < v)
res = max(res, query(seg, id << 1 | 1, mid + 1, r, u, v));
return res;
}
int findFirst(int seg[], int id, int l, int r, int pos, int k) {
if(seg[id] < k || pos > r)
return nArr + 1;
if(pos <= l) {
while(l != r) {
int mid = (l + r) >> 1;
if(seg[id << 1] < k) {
id = id << 1 | 1;
l = mid + 1;
} else {
id = id << 1;
r = mid;
}
}
return l;
}
int res(nArr + 1);
int mid = (l + r) >> 1;
res = min(res, findFirst(seg, id << 1, l, mid, pos, k));
res = min(res, findFirst(seg, id << 1 | 1, mid + 1, r, pos, k));
return res;
}
int calcDP(void) {
int MAX_HORSE(1);
for (int i = 1; i <= nArr; ++i)
MAX_HORSE *= X[i];
for (int i = 0; i <= nArr; ++i) {
for (int k = 0; k <= MAX_HORSE; ++k)
dp[i][k] = -1;
}
dp[0][1] = 0;
for (int i = 0; i < nArr; ++i) {
for (int k = 0; k <= MAX_HORSE; ++k) {
if(dp[i][k] < 0)
continue;
maximize(dp[i + 1][k * X[i + 1]], dp[i][k]);
}
for (int k = MAX_HORSE; k > 0; --k) {
if(dp[i + 1][k] < 0)
continue;
maximize(dp[i + 1][k - 1], dp[i + 1][k] + Y[i + 1]);
}
}
return dp[nArr][0];
}
int calc(void) {
int l(1), r(nArr), opt(1);
while(l <= r) {
int mid = (l + r) >> 1;
if(getx(mid) > 1e9) {
opt = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
ll res = query(1, opt), ans(Y[opt]), prod(1);
while(opt <= nArr) {
int nxt = findFirst(segx, 1, 1, nArr, opt + 1, 2);
ans = max(ans, prod * query(segy, 1, 1, nArr, opt, nxt - 1));
prod *= X[nxt];
opt = nxt;
}
/*if(res * ans != calcDP()) {
cout << "WRONG ANSWER ! JURY: " << calcDP() << ' ' << " FIND: " << res * ans << '\n';
exit(0);
}*/
return res * (ans % modl) % modl;
}
int init(int _N, int _X[], int _Y[]) {
nArr = _N;
for (int i = 1; i <= nArr; ++i) {
X[i] = _X[i - 1];
Y[i] = _Y[i - 1];
fen[i] = 1;
}
build(segx, 1, 1, nArr, X);
build(segy, 1, 1, nArr, Y);
for (int i = 1; i <= nArr; ++i)
modify(i, X[i]);
return calc();
}
int updateX(int pos, int val) {
++pos;
modify(pos, powermod(X[pos], modl - 2) * val % modl);
update(segx, pos, val);
X[pos] = val;
return calc();
}
int updateY(int pos, int val) {
Y[++pos] = val;
update(segy, pos, val);
return calc();
}
Compilation message
horses.cpp:165:2: error: extended character is not valid in an identifier
165 | if(seg[id] < k || pos > r)
| ^
horses.cpp:165:5: error: extended character is not valid in an identifier
165 | if(seg[id] < k || pos > r)
| ^
horses.cpp:166:2: error: extended character is not valid in an identifier
166 | return nArr + 1;
| ^
horses.cpp:166:5: error: extended character is not valid in an identifier
166 | return nArr + 1;
| ^
horses.cpp:166:8: error: extended character is not valid in an identifier
166 | return nArr + 1;
| ^
horses.cpp:166:11: error: extended character is not valid in an identifier
166 | return nArr + 1;
| ^
horses.cpp:184:2: error: extended character is not valid in an identifier
184 | int mid = (l + r) >> 1;
| ^
horses.cpp:184:5: error: extended character is not valid in an identifier
184 | int mid = (l + r) >> 1;
| ^
horses.cpp:185:2: error: extended character is not valid in an identifier
185 | res = min(res, findFirst(seg, id << 1, l, mid, pos, k));
| ^
horses.cpp:185:5: error: extended character is not valid in an identifier
185 | res = min(res, findFirst(seg, id << 1, l, mid, pos, k));
| ^
horses.cpp: In function 'int get(int)':
horses.cpp:101:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
101 | return res;
| ^~~
horses.cpp: In function 'int getx(int)':
horses.cpp:109:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
109 | return res;
| ^~~
horses.cpp: In function 'int query(int, int)':
horses.cpp:113:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
113 | return 1LL * get(u) * powermod(get(v + 1), modl - 2) % modl;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int findFirst(int*, int, int, int, int, int)':
horses.cpp:165:2: error: '\U000000a0' was not declared in this scope
165 | if(seg[id] < k || pos > r)
| ^
horses.cpp:184:4: error: expected ';' before '\U000000a0int'
184 | int mid = (l + r) >> 1;
| ^~~~~
| ;
horses.cpp:185:4: error: expected ';' before '\U000000a0res'
185 | res = min(res, findFirst(seg, id << 1, l, mid, pos, k));
| ^~~~~
| ;
horses.cpp:187:48: error: 'mid' was not declared in this scope; did you mean 'id'?
187 | res = min(res, findFirst(seg, id << 1 | 1, mid + 1, r, pos, k));
| ^~~
| id
horses.cpp: In function 'int calc()':
horses.cpp:246:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
246 | return res * (ans % modl) % modl;
| ~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:267:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
267 | modify(pos, powermod(X[pos], modl - 2) * val % modl);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
