#include <horses.h>
#include <bits/stdc++.h>
using namespace std;
struct RangeSeg {
int startRange;
int endRange;
int bestY;
bool operator < (RangeSeg const &other) const {
return startRange < other.startRange;
}
};
set <RangeSeg> Intervals;
const int MOD = 1e9 + 7, MAX_N = 5e5;
int N;
int X[1 + MAX_N];
int Y[1 + MAX_N];
struct Bit {
vector <int> aib;
int n;
int lsb (int x) {
return x & -x;
}
void init (int _n) {
n = _n;
aib.resize (n + 1, 1);
}
void upd (int pos, int val) {
while (pos <= n) {
aib[pos] = (1ll * aib[pos] * val) % MOD;
pos += lsb (pos);
}
}
int qry (int pos) {
int ans = 1;
while (pos) {
ans = (1ll * ans * aib[pos]) % MOD;
pos -= lsb (pos);
}
return ans;
}
};
struct SegMax {
vector <int> seg;
int n;
int query (int node, int l, int r, int nl, int nr) {
if (nl <= l && r <= nr)
return seg[node];
int mid = (l + r) / 2;
int ans = 0;
if (mid >= nl)
ans = max (ans, query (2 * node, l, mid, nl, nr));
if (mid < nr)
ans = max (ans, query (2 * node + 1, mid + 1, r, nl, nr));
return ans;
}
void update (int node, int l, int r, int pos, int val) {
if (l == r) {
seg[node] = val;
return;
}
int mid = (l + r) / 2;
if (mid >= pos)
update (2 * node, l, mid, pos, val);
else
update (2 * node + 1, mid + 1, r, pos, val);
seg[node] = max (seg[2 * node], seg[2 * node + 1]);
}
void init (int _n) {
n = _n;
seg.resize (4 * n + 1, 0);
}
void updateVal (int pos, int val) {
update (1, 1, n, pos, val);
}
int queryRange (int l, int r) {
return query (1, 1, n, l, r);
}
};
SegMax MaxY;
Bit aibMOD;
const int MAGIC = 30;
typedef long double ld;
typedef long long ll;
const ld EPS = 1e-12;
int getAns () {
int NoSeg = 0;
auto it = Intervals.end ();
it = prev (it);
ll xTot = 1;
ll bestX = 0;
int bestY = 0;
int bestMOD = 0;
while (NoSeg < min (MAGIC, (int) Intervals.size ())) {
RangeSeg x = *it;
/// bestY / xTot > best
if (bestMOD == 0 || (1ll * x.bestY * bestX > 1ll * bestY * xTot)) {
bestX = xTot;
bestY = x.bestY;
bestMOD = 1ll * aibMOD.qry (x.startRange) * x.bestY % MOD;
}
xTot *= X[x.startRange];
if (xTot > (1ll << 30))
return bestMOD;
it = prev (it);
NoSeg++;
}
return bestMOD;
}
int lgput (int a, int b) {
int ans = 1;
while (b) {
if (b & 1)
ans = 1ll * ans * a % MOD;
a = 1ll * a * a % MOD;
b /= 2;
}
return ans;
}
int inv (int x) {
return lgput (x, MOD - 2);
}
void split (set <RangeSeg>::iterator it, int pos) {
RangeSeg x = *it;
if (pos == x.startRange) return;
Intervals.erase (it);
RangeSeg x1 = {x.startRange, pos - 1, MaxY.queryRange (x.startRange, pos - 1)},
x2 = {pos, x.endRange, MaxY.queryRange (pos, x.endRange)};
Intervals.insert (x1);
Intervals.insert (x2);
}
void join (set <RangeSeg>::iterator it1, set <RangeSeg>::iterator it2) {
RangeSeg x1 = *it1,
x2 = *it2;
Intervals.erase (it1);
Intervals.erase (it2);
RangeSeg x = {x1.startRange, x2.endRange, MaxY.queryRange (x1.startRange, x2.endRange)};
Intervals.insert (x);
}
int updateX (int pos, int val) {
aibMOD.upd (pos, inv (X[pos]));
aibMOD.upd (pos, val);
if (val == 1) {
if (X[pos] != 1) {
set <RangeSeg>::iterator it2 = Intervals.lower_bound ({pos, 0, 0});
if (it2 != Intervals.begin ()) {
set <RangeSeg>::iterator it1 = prev (it2);
join (it1, it2);
}
}
}
else {
if (X[pos] == 1) {
set <RangeSeg>::iterator it = Intervals.lower_bound ({pos + 1, 0, 0});
it = prev (it);
split (it, pos);
}
}
X[pos] = val;
return getAns ();
}
int updateY (int pos, int val) {
MaxY.updateVal (pos, val);
set <RangeSeg>::iterator it = Intervals.lower_bound ({pos + 1, 0, 0});
it = prev (it);
/// why???
auto x = *it;
Intervals.erase (it);
x.bestY = MaxY.queryRange (x.startRange, x.endRange);
Intervals.insert (x);
return getAns ();
}
int init (int n, int x[], int y[]) {
N = n;
for (int i = 1; i <= N; i++)
X[i] = x[i], Y[i] = y[i];
MaxY.init (N);
for (int i = 1; i <= N; i++)
MaxY.updateVal (i, Y[i]);
aibMOD.init (N);
int startIndex = 1;
for (int i = 1; i <= N; i++) {
aibMOD.upd (i, X[i]);
if (X[i] > 1) {
if (i > 1)
Intervals.insert ({startIndex, i - 1, MaxY.queryRange (startIndex, i - 1)});
startIndex = i;
}
}
Intervals.insert ({startIndex, n, MaxY.queryRange (startIndex, n)});
// for (auto x : Intervals) {
// cout << x.startRange << " " << x.endRange << " " << x.bestY << "\n";
// }
return getAns ();
}
/**
5
1 2 1 1 2
2 3 4 5 6
4
2 3 20
1 2 1
2 3 1
1 3 5
**/
/*int x[1 + MAX_N], y[1 + MAX_N];
int main () {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> x[i];
for (int i = 1; i <= n; i++)
cin >> y[i];
cout << init (n, x, y) << "\n";
int m;
cin >> m;
for (int i = 1; i <= m; i++) {
int pos, val, type;
cin >> type >> pos >> val;
if (type == 1)
cout << updateX (pos, val) << "\n";
else
cout << updateY (pos, val) << "\n";
}
return 0;
}*/
Compilation message
horses.cpp: In member function 'void Bit::upd(int, int)':
horses.cpp:40:47: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
aib[pos] = (1ll * aib[pos] * val) % MOD;
~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int Bit::qry(int)':
horses.cpp:47:42: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
ans = (1ll * ans * aib[pos]) % MOD;
~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int getAns()':
horses.cpp:116:65: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
bestMOD = 1ll * aibMOD.qry (x.startRange) * x.bestY % MOD;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int lgput(int, int)':
horses.cpp:135:33: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
ans = 1ll * ans * a % MOD;
~~~~~~~~~~~~~~^~~~~
horses.cpp:136:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
a = 1ll * a * a % MOD;
~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
399 ms |
50296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
