| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 108449 | MetB | 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 <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>
#include <string.h>
#include <random>
typedef long long ll;
const ll MOD = 1e9 + 7, INF = 1e18;
using namespace std;
set < pair <int, ll> > s;
ll n, X[500000], m, Y[500000], ans;
ll qmult (ll a, ll b)
{
ll s = 0;
while (b)
{
if (b % 2) s = (s + a) % MOD;
b /= 2;
a = (a + a) % MOD;
}
return s;
}
struct SegTree
{
ll t[2000000], start, type;
void build (int n, int d)
{
start = 1;
type = d;
while (start < n) start <<= 1;
for (int i = 0; i < n; i++)
t[start + i] = (type ? Y[i] : X[i]);
for (int i = start - 1; i; i--)
t[i] = (type ? max (t[2 * i], t[2 * i + 1]) : t[2 * i] * t[2 * i + 1] % MOD);
}
void update (int x, ll d)
{
x += start;
t[x] = d;
x /= 2;
while (x)
{
if (type) t[x] = max (t[2 * x], t[2 * x + 1]);
else t[x] = t[2 * x] * t[2 * x + 1] % MOD;
x /= 2;
}
}
ll get (int l, int r)
{
ll sum = (type ? -INF : 1);
l += start;
r += start + 1;
while (l < r)
{
if (l & 1) sum = (type ? max (sum, t[l++]) : sum * t[l++] % MOD);
if (r & 1) sum = (type ? max (sum, t[--r]) : sum * t[--r] % MOD);
l >>= 1;
r >>= 1;
}
return sum;
}
ll& operator [] (const int& i)
{
return t[i + start];
}
} t, tm;
ll find_answer (set < pair <int, ll> > :: iterator st)
{
ans = 0;
ll mul = 1;
if (st -> first)
{
if (st == s.begin ())
{
ans = t.get (0, st -> first - 1);
}
else
{
auto k = st;
k--;
ans = t.get (k -> first, st -> first - 1);
}
}
for (auto it = st; it != s.end (); it++)
{
mul *= it -> second;
auto prev = it;
it++;
if (it == s.end ()) ans = max (ans, mul * t.get (prev -> first, n - 1));
else ans = max (ans, mul * t.get (prev -> first, it -> first - 1));
it = prev;
}
if (s.empty ()) return t.get (0, n - 1) % MOD;
else
{
auto k = st;
if (k == s.begin ()) return ans % MOD;
else
{
k--;
return qmult (ans, tm.get (0, k -> first)) % MOD;
}
}
}
set < pair <int, ll> > :: iterator new_start ()
{
auto st = s.end ();
if (!s.empty ())
{
st--;
ll mul = 1;
while (mul != INF)
{
if (mul >= 1000000000LL && st -> second >= 1000000000LL) mul = INF;
else if ((mul * st -> second) > 1000000000LL) mul = INF;
if (mul == INF) break;
if (st == s.begin ()) break;
mul *= st -> second;
st--;
}
if (mul == INF) st++;
}
return st;
}
ll init (int n, vector <ll> a_X, vector <ll> a_Y)
{
for (int i = 0; i < n; i++)
{
X[i] = a_X[i];
if (X[i] != 1) s.insert (make_pair (i, X[i]));
}
for (int i = 0; i < n; i++)
Y[i] = a_Y[i];
t.build (n, 1);
tm.build (n, 0);
auto st = new_start ();
return find_answer (st);
}
ll updateX (ll ind, ll v)
{
if (X[ind] != 1)
s.erase (make_pair (ind, X[ind]));
if (v != 1)
s.insert (make_pair (ind, v));
X[ind] = v;
tm.update (ind, v);
st = new_start ();
return find_answer (st);
}
ll updateY (ll ind, ll v)
{
t.update (ind, v);
return find_answer (st);
}