| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1138122 | Ekber_Ekber | Horses (IOI15_horses) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define count1 __builtin_popcount
#define all(v) v.begin(), v.end()
using namespace std;
struct point{
int ans, sum;
};
int ctoi(char x) {
return (int)x - '0';
}
int sumab(int a, int b) {
return (a + b) * (b - a + 1) / 2;
}
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a%b);
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
void print(vector <int> &v) {
for (const int &i : v) cout << i << " ";
}
constexpr int MAX = 5e+5 + 3, INF = 2e+9, MOD = 1e+9 + 7, K = log2(MAX);
vector <int> a, b;
vector <point> t(4 * MAX);
void build(int v, int tl, int tr) {
if (tl == tr) {
t[v].ans = (a[tl] * b[tl]) % MOD;
t[v].sum = a[tl];
return;
}
int tm = (tl + tr) / 2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD;
t[v].ans = max(t[v*2].ans, (t[v*2].sum * t[v*2+1].ans) % MOD);
}
point find(int v, int tl, int tr, int l, int r) {
if (l > r) return {INF, INF};
if (tl == l && tr == r) return t[v];
int tm = (tl + tr) / 2;
point res1 = find(v*2, tl, tm, l, min(r, tm));
point res2 = find(v*2+1, tm+1, tr, max(l, tm+1), r);
point res;
res.sum = (res1.sum * res2.sum) % MOD;
res.ans = max(res1.ans, (res1.sum * res2.ans) % MOD);
return res;
}
void updatex(int v, int tl, int tr, int i, int x) {
if (tl == tr) {
t[v].ans = (x * b[tl]) % MOD;
t[v].sum = x;
a[tl] = x;
return;
}
int tm = (tl + tr) / 2;
if (i <= tm) {
updatex(v*2, tl, tm, i, x);
}
else {
updatex(v*2+1, tm+1, tr, i, x);
}
t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD;
t[v].ans = max(t[v*2].ans, (t[v*2].sum * t[v*2+1].ans) % MOD);
}
void updatey(int v, int tl, int tr, int i, int y) {
if (tl == tr) {
t[v].ans = (a[tl] * y) % MOD;
b[tl] = y;
return;
}
int tm = (tl + tr) / 2;
if (i <= tm) {
updatey(v*2, tl, tm, i, y);
}
else {
updatey(v*2+1, tm+1, tr, i, y);
}
t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD;
t[v].ans = max(t[v*2].ans, (t[v*2].sum * t[v*2+1].ans) % MOD);
}
void _() {
int n, q;
cin >> n;
a.resize(n); b.resize(n);
for (int &i : a) {
cin >> i;
}
for (int &i : b) {
cin >> i;
}
build(1, 0, n-1);
cin >> q;
while (q--) {
int d;
cin >> d;
if (d == 1) {
int i, x;
cin >> i >> x;
updatex(1, 0, n-1, i, x);
cout << t[1].ans << endl;
}
else {
int i, x;
cin >> i >> x;
updatey(1, 0, n-1, i, x);
cout << t[1].ans << endl;
}
}
}
signed main() {
// GOOD_LUCK
int tests=1;
// cin >> tests;
while (tests--) {
_();
// cout << endl;
}
return 0;
}
// Problem X
// by Ekber_Ekber