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"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 4e18;
int n, A[N], B[N];
struct node
{
ll z, mx, my;
void init(int a, int b)
{
z = a;
mx = a;
my = b;
}
friend node operator | (node a, node b)
{
node ret;
ret.z = a.z * b.z % mod;
ret.mx = max(a.mx, b.mx);
ret.my = max(a.my, b.my);
return ret;
}
} seg[N << 2];
void build(int v = 1, int tl = 0, int tr = n - 1)
{
if(tl == tr)
{
seg[v].init(A[tl], B[tl]);
return;
}
int mid = (tl + tr) >> 1;
build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
seg[v] = seg[v << 1] | seg[v << 1 | 1];
}
void Change(int p, int v = 1, int tl = 0, int tr = n - 1)
{
if(tl == tr)
{
seg[v].init(A[p], B[p]);
return;
}
int mid = (tl + tr) >> 1;
if(p <= mid) Change(p, v << 1, tl, mid);
else Change(p, v << 1 | 1, mid + 1, tr);
seg[v] = seg[v << 1] | seg[v << 1 | 1];
}
pii get(int pos, int v = 1, int tl = 0, int tr = n - 1)
{
if(tl > pos) return Mp(-1, -1);
if(seg[v].mx == 1) return Mp(tl, seg[v].my);
if(tl == tr) return Mp(tl, B[tl]);
int mid = (tl + tr) >> 1;
pii cu = get(pos, v << 1 | 1, mid + 1, tr);
if(A[cu.F] > 1)
{
return cu;
}
pii now = get(pos, v << 1, tl, mid);
return Mp(now.F, max(now.S, cu.S));
}
ll ask(int l, int r, int v = 1, int tl = 0, int tr = n - 1)
{
if(l > tr || r < tl || l > r) return 1;
if(l <= tl && tr <= r) return seg[v].z;
int mid = (tl + tr) >> 1;
return ask(l, r, v << 1, tl, mid) * ask(l, r, v << 1 | 1, mid + 1, tr) % mod;
}
int solve()
{
int id = n - 1;
ll zarb = 1, best = 0;
while(id >= 0)
{
pii now = get(id);
zarb *= A[now.F];
best = max(best, (ll)now.S);
assert(id > now.F - 1);
id = now.F - 1;
assert(id >= -1);
///printf("id = %d best = %lld zarb = %lld\n", id, best, zarb);
if(zarb >= mod) break;
best *= A[now.F];
assert(best <= inf);
}
///printf("at the end best = %lld\n", best);
best %= mod;
if(id == -1)
{
return best;
}
///printf("now best = %lld id = %d ask = %lld\n", best, id, ask(0, id + 1));
return best * ask(0, id + 1) % mod;
}
int init(int _N, int X[], int Y[])
{
/*ll c = 1000000000;
c = c * c % mod;
cout << c << " " << c * c % mod << endl;*/
n = _N;
for(int i = 0; i < n; i ++) A[i] = X[i], B[i] = Y[i];
build();
return solve();
}
int updateX(int pos, int val)
{
assert(val > 0);
A[pos] = val;
Change(pos);
return solve();
}
int updateY(int pos, int val)
{
assert(val > 0);
B[pos] = val;
Change(pos);
return solve();
}
Compilation message (stderr)
horses.cpp: In function 'int solve()':
horses.cpp:116:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
116 | return best;
| ^~~~
horses.cpp:119:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
119 | return best * ask(0, id + 1) % mod;
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |