#include <bits/stdc++.h>
#include "horses.h"
#define N 500010
using namespace std;
int n;
long long v[N][2];
long long dp[N];
const long long mod = 1e9+7;
long long p = 1;
long long binpow(long long a, long long b, long long m){
// cout << a << ' ';
a %= m;
if(b == 0) return 1;
long long t = binpow(a, b/2, m);
if(b % 2 == 0) return (t*t) % m;
else return ((((t*t) % m)*a) % m);
}
struct Segtree{
long long tree[4*N];
long long join(long long a, long long b){
return (a*b) % mod;
}
void build(int node, int l, int r){
if(l == r){
tree[node] = v[l][0];
return;
}
int mid = (l+r) >> 1;
build(2*node,l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
void update(int node, int l, int r, int pos, long long val){
if(l == r){
tree[node] = val;
return;
}
int mid = (l+r)/2;
if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
else update(2*node, mid+1, r, pos, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
long long query(int node, int l, int r, int tl, int tr){
if(l <= tl and tr <= r) return tree[node];
if(l > tr or tl > r) return 1;
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
} seg;
int solve(){
if(n <= 40){
dp[0] = 0;
long long res = 0;
for(int i = 1;i <= n;i++){
dp[i] = 0;
long long int prod = 1;
for(int j = i;j > 0;j--){
prod *= v[j][0];
dp[i] = max(dp[i], dp[j-1] + ((prod-1)*v[i][1]));
res = max(res, dp[j-1] + prod*v[i][1]);
}
// cout << dp[i] << ' ';
}
return res % mod;
}
long long prod = 1;
int fim = n;
for(int i = n-1;i > n-40;i--){
prod *= v[n+1][0];
if(prod > 1e9+7) break;
if(prod*v[fim][1] < v[i][1]){
fim = i;
prod = 1;
}
}
return seg.query(1, 1, fim, 1, n);
}
int init(int NN, int X[], int Y[]) {
n = NN;
for(int i = 1;i <= n;i++){
v[i][0] = X[i-1];
p *= v[i][0];
p %= mod;
v[i][1] = Y[i-1];
}
seg.build(1, 1, n);
cout << n << ' ';
return solve();
}
int updateX(int pos, int val) {
v[pos+1][0] = val;
seg.update(1, 1, n, pos+1,val);
return solve();
}
int updateY(int pos, int val) {
v[pos+1][1] = val;
return solve();
}
Compilation message
horses.cpp: In function 'int solve()':
horses.cpp:72:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
72 | return res % mod;
| ~~~~^~~~~
horses.cpp:78:6: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
78 | if(prod > 1e9+7) break;
| ^~~~
horses.cpp:84:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
84 | return seg.query(1, 1, fim, 1, n);
| ~~~~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
22352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
