| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 988755 | bigo | 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.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <utility>
using namespace std;
#define all(a) a.begin(), a.end()
#define rep(i,s,e) for(ll i=s;i<e;i++)
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = 1e18;
typedef complex<double> cd;
const double pi = acos(-1);
const ll mod = 1e9 + 7;
const ll mod1 = 1e9 + 9;
const ll mod2 = 998244353;
const ll mac = 31;
const int MAXN = 4e5 + 2;
typedef vector<int> vi;
typedef vector<vi> vvi;
vi x, y;
int cef(int a, int b) {
int val;
if (ll(a) * ll(b) >= 1e9)
val = 0;
else
val = a*b;
return val;
}
struct seg {
int l, r, mid, val=1;
seg* lp, * rp;
seg(int l, int r): l(l), r(r), mid((l + r) / 2) {
if (l < r) {
lp = new seg(l, mid);
rp = new seg(mid+1,r);
}
}
void pull() {
val = cef(lp->val, rp->val);
}
void upd(int i,int x) {
if (l == r) {
val = x;
return;
}
if (i <= mid) lp->upd(i, x);
else rp->upd(i, x);
pull();
}
int que(int a, int b) {
if (a <= l and r <= b) return val;
if (a > r or l > b) return 1;
return cef(lp->que(a, b),rp->que(a, b));
}
};
int n;
int init(int N, int X[], int Y[]) {
n = N;
x.resize(n);
y.resize(n);
rep(i, 0, n) x[i] = X[i], y[i] = Y[i];
pair<int, int>ans = {0,(x[0]*y[0])%mod};
int c = x[0];
seg segx(0, n - 1);
rep(i, 1, n) {
segx.upd(i, x[i]);
c *= x[i];
c %= mod;
int t = cef(segx.que(ans.first + 1, i), y[i]);
if (t == 0 or t >= y[ans.first])
ans = { i,(c * y[i]) % mod };
}
return ans.second;
}
int updateX(int pos, int val) {
x[pos] = val;
pair<int, int>ans = { 0,(x[0] * y[0]) % mod };
int c = x[0];
seg segx(0, n - 1);
rep(i, 1, n) {
segx.upd(i, x[i]);
c *= x[i];
c %= mod;
int t = cef(segx.que(ans.first + 1, i), y[i]);
if (t == 0 or t >= y[ans.first])
ans = { i,(c * y[i]) % mod };
}
return ans.second;
}
int updateY(int pos, int val) {
y[pos] = val;
pair<int, int>ans = { 0,(x[0] * y[0]) % mod };
int c = x[0];
seg segx(0, n - 1);
rep(i, 1, n) {
segx.upd(i, x[i]);
c *= x[i];
c %= mod;
int t = cef(segx.que(ans.first + 1, i), y[i]);
if (t == 0 or t >= y[ans.first])
ans = { i,(c * y[i]) % mod };
}
return ans.second;
}
int main() {
int n, q;
cin >> n >> q;
int x[3],y[3];
rep(i, 0, n)
cin >> x[i];
rep(i, 0, n)
cin >> y[i];
cout << init(n, x, y);
while (q--) {
int t, pos, val;
cin >> t >> pos >> val;
if (t == 1)
cout << updateX(pos, val);
else
cout << updateY(pos, val);
}
}