| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 246524 | Artyom123 | Horses (IOI15_horses) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define ll long long
#define ld long double
const int INF = 2e9 + 1;
const ll INFLL = 1e18 + 1;
const int mod = 1e9 + 7;
vector<int> t;
void build(int v, int vl, int vr, vector<ll> &a) {
if (vr - vl == 1) {
t[v] = a[vl];
return;
}
int vm = (vl + vr) / 2;
build(2 * v + 1, vl, vm, a);
build(2 * v + 2, vm, vr, a);
t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}
void modify(int v, int vl, int vr, int ind, int val) {
if (vr - vl == 1) {
t[v] = val;
return;
}
int vm = (vl + vr) / 2;
if (ind < vm) modify(2 * v + 1, vl, vm, ind, val);
else modify(2 * v + 2, vm, vr, ind, val);
t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}
int get(int v, int vl, int vr, int l, int r) {
if (r <= vl || l >= vr) return 0;
if (vl >= l && vr <= r) return t[v];
int vm = (vl + vr) / 2;
return max(get(2 * v + 1, vl, vm, l, r),
get(2 * v + 2, vm, vr, l, r));
}
struct segment{
int l, r, mx;
segment(){}
segment(int l, int r, int mx) : l(l), r(r), mx(mx) {}
bool operator< (const segment &a) const {
return l < a.l;
}
};
ll total = 1;
ll my_pow(ll n, ll m) {
if (m == 0) return 1;
ll now = my_pow(n, m / 2);
if (m % 2 == 0) return (now * now) % mod;
return (((now * now) % mod) * n) % mod;
}
set<segment> s;
vector<ll> x, y;
int solve() {
auto it = s.end();
int ind = -1;
ll now = 1;
ll suff = 1;
for (int i = 0; i < 70 && it != s.begin(); i--) {
it--;
ll x1 = x[it->l], y1 = y[it->mx];
if (y1 >= now) {
ind = i;
}
if (x1 * y1 > 1e9) {
ind = i;
break;
}
if (now * x1 > 1e9) {
ind = i;
break;
}
now = max(now * x1, x1 * y1);
}
ll ans = 0;
it = s.end();
for (int i = 0; ; i--) {
it--;
if (i == ind) {
ans = (total * my_pow(suff, mod - 2)) % mod;
ans *= it->mx;
ans %= mod;
break;
}
suff *= x[it->l];
suff %= mod;
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
x.resize(n);
for (auto &c : x) cin >> c;
t.resize(4 * n);
y.resize(n);
for (auto &c : y) cin >> c;
build(0, 0, n, y);
vector<pair<int, int>> seg;
for (int i = 0; i < n; i++) {
total *= x[i];
total %= mod;
if (x[i] >= 2) {
seg.pb(i, i);
continue;
}
if (i == 0 || x[i] == x[i - 1]) {
seg.back().se++;
continue;
}
seg.pb(i, i);
}
for (auto &c : seg) {
s.insert(segment(c.fi, c.se, get(0, 0, n, c.fi, c.se + 1)));
}
cout << solve() << "\n";
int m;
cin >> m;
while (m--) {
int type;
cin >> type;
if (type == 1) {
int pos, val;
cin >> pos >> val;
total *= my_pow(x[pos], mod - 2);
total %= mod;
total *= val;
total %= mod;
segment lol(pos, pos, 0);
auto it = s.upper_bound(lol);
it--;
if (x[pos] == val) continue;
if (x[pos] > 1 && val > 1) {
x[pos] = val;
continue;
}
if (x[pos] == 1 && val > 1) {
x[pos] = val;
segment now = *it;
int l = now.l, r = now.r;
if (now.l == now.r) {
continue;
}
if (pos == now.l) {
s.erase(it);
s.insert(segment(pos, pos, get(0, 0, n, pos, pos + 1)));
s.insert(segment(l + 1, r, get(0, 0, n, l + 1, r + 1)));
continue;
}
if (pos == now.r) {
s.erase(it);
s.insert(segment(pos, pos, get(0, 0, n, pos, pos + 1)));
s.insert(segment(l, r - 1, get(0, 0, n, l, r)));
continue;
}
s.erase(it);
s.insert(segment(l, pos - 1, get(0, 0, n, l, pos)));
s.insert(segment(pos, pos, get(0, 0, n, pos, pos + 1)));
s.insert(segment(pos + 1, r, get(0, 0, n, pos + 1, r + 1)));
continue;
}
if (x[pos] > 1 && val == 1) {
x[pos] = val;
segment now = *it;
int l = now.l, r = now.r;
if (now.l != 0 && x[now.l - 1] == 1) {
it--;
l = it->l;
s.erase(it);
it++;
}
if (now.r != n - 1 && x[now.r + 1] == 1) {
it++;
r = it->r;
s.erase(it);
it--;
}
s.erase(it);
now.l = l, now.r = r;
now.mx = get(0, 0, n, l, r + 1);
s.insert(now);
}
} else {
int pos, val;
cin >> pos >> val;
modify(0, 0, n, pos, val);
segment lol(pos, pos, 0);
auto it = s.upper_bound(lol);
it--;
segment now = *it;
s.erase(it);
now.mx = get(0, 0, n, now.l, now.r + 1);
s.insert(now);
}
cout << solve() << "\n";
}
return 0;
}