#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 545 , inf = 1e9 + 12 , mod = 1e9 + 7;
#include "horses.h"
struct segtree {
int tree[N*4];
void update(int v,int l,int r,int pos,int val) {
if(l == r) {
tree[v] = val;
return;
}
int mid = (l+r)/2;
if(pos <= mid) {
update((v << 1 | 1), l, mid, pos, val);
}
else {
update((v << 1 | 1), mid + 1, r, pos, val);
}
tree[v] = max(tree[(v << 1)], tree[(v << 1 | 1)]);
}
int get(int v,int l,int r,int ml,int mr) {
if(mr < l || r < ml || l > r){
return 0LL;
}
if(ml <= l && r <= mr){
return tree[v];
}
int mid = (l+r)/2;
return max(get((v << 1), l, mid, ml, mr), get((v << 1 | 1), mid + 1, r, ml, mr));
}
};
int n;
ll x[N] , y[N];
set<int> s;
ll tmp = 1;
ll bp(ll x,ll m){
if(m == 0){
return 1LL;
}
if(m == 1){
return x%mod;
}
if(m%2==0){
return bp(x*x%mod,m/2)%mod;
}
return x*bp(x,m-1)%mod;
}
segtree S;
int calc() {
ll res = 1 , ind = -1;
assert((int)s.size() >= 2);
auto it = next(s.rbegin());
while(it != s.rend()) {
res *= x[*it];
ind = *it;
if(res > inf){
break;
}
it = next(it);
}
auto it2 = s.lower_bound(ind);
ll mx = 0;
res = 1;
while(next(it2) != s.end()) {
int i = *it2;
int j = *(next(it2));
if(i != ind){
res = res*x[i];
}
mx = max(mx, res * S.get(1, 0, n-1, i, j-1));
it2 = next(it2);
}
mx %= mod;
return tmp*bp(res,mod-2)%mod*mx%mod;
}
int init(int nn, int X[], int Y[]) {
n = nn;
for(int i=0;i<n;i++) {
x[i] = X[i];
y[i] = Y[i];
}
for(int i=0;i<n;i++) {
S.update(1, 0, n - 1, i, y[i]);
}
s.insert(0);
s.insert(n);
for(int i=n-1;i>=0;i--) {
if(x[i] > 1) {
tmp = (tmp * x[i])%mod;
s.insert(i);
}
}
return calc();
}
int updateX(int pos, int val) {
tmp = (tmp * bp(x[pos], mod-2))%mod;
x[pos] = val;
tmp = (tmp*val)%mod;
if(val > 1 || pos == 0){
s.insert(pos);
}
else{
assert(s.find(pos) != s.end());
s.erase(s.find(pos));
}
return calc();
}
int updateY(int pos, int val) {
S.update(1, 0, n-1, pos, val);
return calc();
}
Compilation message
horses.cpp: In function 'll bp(ll, ll)':
horses.cpp:44:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
44 | ll bp(ll x,ll m){
| ~~~^
horses.cpp:40:4: note: shadowed declaration is here
40 | ll x[N] , y[N];
| ^
horses.cpp: In function 'int calc()':
horses.cpp:72:27: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::key_type' {aka 'int'} may change value [-Wconversion]
72 | auto it2 = s.lower_bound(ind);
| ^~~
horses.cpp:85:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
85 | return tmp*bp(res,mod-2)%mod*mx%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:96:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
96 | S.update(1, 0, n - 1, i, y[i]);
| ~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4548 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
464 ms |
45388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
