| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 403145 | ruadhan | Horses (IOI15_horses) | C++17 | 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 "horses.h"
#include <bits/stdc++.h>
typedef long long ll;
#define sz(x) (int)x.size()
using namespace std;
const int MOD = 1e9 + 7;
const int MX = 5e5 + 5;
int N;
ll X[MX], Y[MX];
struct ModVal
{
ll div = 0, mod = 0;
ModVal(ll _div, ll _mod)
{
div = _div;
mod = _mod;
}
bool operator<(const ModVal &other) const
{
if (div == other.div)
return mod < other.mod;
return div < other.div;
}
ModVal operator*(const ModVal &other)
{
ModVal ret(0, 0);
ret.div = div * other.div;
ret.mod = (mod * other.mod) % MOD;
ret.div += ((mod * other.mod) / MOD) % MOD;
return ret;
}
ModVal operator*(const ll &integer)
{
ModVal ret(0, 0);
ret.div = div + ((mod * integer) / MOD);
ret.mod = (mod * integer) % MOD;
return ret;
}
};
template <class T>
struct SegMax
{
const T ID = {0, 0};
T comb(T a, T b) { return max(a, b); }
int n;
vector<T> seg;
void init(int _n)
{
n = _n;
seg.assign(2 * n, ID);
}
void pull(int p)
{
seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
}
void upd(int p, T val)
{
seg[p += n] = val;
for (p /= 2; p; p /= 2)
pull(p);
}
T query(int l, int r)
{
T ra = ID, rb = ID;
for (l += n, r += n + 1; l < r; l /= 2, r /= 2)
{
if (l & 1)
ra = comb(ra, seg[l++]);
if (r & 1)
rb = comb(seg[--r], rb);
}
return comb(ra, rb);
}
};
SegMax<ModVal> mx;
template <class T>
struct SegMul
{
const T ID = {0, 1};
T comb(T a, T b) { return (a * b); }
int n;
vector<T> seg;
void init(int _n)
{
n = _n;
seg.assign(2 * n, ID);
}
void pull(int p)
{
seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
}
void upd(int p, T val)
{
int pos = p;
seg[p += n] = val;
for (p /= 2; p; p /= 2)
pull(p);
mx.upd(pos, query(1, pos) * Y[pos - 1]);
}
T query(int l, int r)
{
T ra = ID, rb = ID;
for (l += n, r += n + 1; l < r; l /= 2, r /= 2)
{
if (l & 1)
ra = comb(ra, seg[l++]);
if (r & 1)
rb = comb(seg[--r], rb);
}
return comb(ra, rb);
}
};
SegMul<ModVal> mul;
int init(int N, vector<int> X, vector<int> Y)
{
::N = N;
for (int i = 0; i < sz(X); i++)
::X[i] = X[i];
for (int i = 0; i < sz(Y); i++)
::Y[i] = Y[i];
mx.init(N + 1), mul.init(N + 1);
for (int i = 1; i <= N; i++)
mul.upd(i, ModVal(0, X[i - 1]));
return mx.query(1, N).mod;
}
int updateX(int pos, int val)
{
X[pos - 1] = val;
mul.upd(pos, ModVal(0, val));
return mx.query(1, N).mod;
}
int updateY(int pos, int val)
{
Y[pos - 1] = val;
mx.upd(pos, mul.query(1, pos) * Y[pos - 1]);
return mx.query(1, N).mod;
}
// int main()
// {
// int n, m;
// cin >> n >> m;
// vector<int> a1(n), a2(n);
// for (auto &x : a1)
// cin >> x;
// for (auto &x : a2)
// cin >> x;
// cout << init(n, a1, a2) << '\n';
// // for (auto x : mx.seg)
// // cout << x.mod << " ";
// // cout << '\n';
// // for (auto x : mul.seg)
// // cout << x.mod << " ";
// // cout << '\n';
// while (m--)
// {
// int a, b, c;
// cin >> a >> b >> c;
// b++;
// if (a == 1)
// {
// cout << updateX(b, c) << '\n';
// }
// else
// {
// cout << updateY(b, c) << '\n';
// }
// }
// // for (auto x : mx.seg)
// // cout << x.mod << " ";
// // cout << '\n';
// // for (auto x : mul.seg)
// // cout << x.mod << " ";
// // cout << '\n';
// // cout << mul.query(1, 2).mod << '\n';
// return 0;
// }