#include<bits/stdc++.h>
#include "horses.h"
#define MAXN 500007
using namespace std;
const long long mod=1e9+7;
struct ST{
int tree[4*MAXN];
long long mult[4*MAXN];
void update(int v,int l,int r,int pos,int val){
if(l==r){
tree[v]=val;
mult[v]=val;
}else{
int tt=(l+r)/2;
if(pos<=tt)update(2*v,l,tt,pos,val);
else update(2*v+1,tt+1,r,pos,val);
tree[v]=max(tree[2*v],tree[2*v+1]);
mult[v]=(mult[2*v]*mult[2*v+1])%mod;
}
}
int getmax(int v,int l,int r,int ll,int rr){
if(ll>rr)return 0;
if(l==ll and r==rr){
return tree[v];
}else{
int tt=(l+r)/2;
return max( getmax(2*v,l,tt,ll,min(tt,rr)) , getmax(2*v+1,tt+1,r,max(tt+1,ll),rr) );
}
}
int solve(int v,int l,int r){
if(l==r)return l;
int tt=(l+r)/2;
if(tree[2*v+1]>1)return solve(2*v+1,tt+1,r);
return solve(2*v,l,tt);
}
int findpos(int v,int l,int r,int ll,int rr){
if(ll>rr)return 0;
if(l==ll and r==rr){
if(tree[v]>1)return solve(v,l,r);
return 0;
}else{
int tt=(l+r)/2;
int curr=findpos(2*v+1,tt+1,r,max(tt+1,ll),rr);
if(curr!=0)return curr;
return findpos(2*v,l,tt,ll,min(tt,rr));
}
}
long long getmult(int v,int l,int r,int ll,int rr){
if(ll>rr)return 1;
if(l==ll and r==rr)return mult[v];
int tt=(l+r)/2;
return (getmult(2*v,l,tt,ll,min(tt,rr)) * getmult(2*v+1,tt+1,r,max(tt+1,ll),rr))%mod;
}
}xs,ys;
int n;
long long x[MAXN],y[MAXN];
int calc(){
long long mult=1,res=0,ans=0;
int to=n+1;
vector< pair<int,int> > w;
while(to>1 and mult<mod){
int s=xs.findpos(1,1,n,1,to-1);
if(s==0){
w.push_back({1,to-1}); break;
}else{
w.push_back({s,to-1}); to=s;
mult*=x[s];
}
}
mult=1;
for(int i=w.size()-1;i>=0;i--){
long long curr=(long long) mult*ys.getmax(1,1,n,w[i].first,w[i].second);
if(curr>res){
res=curr;
ans=((res%mod)*xs.getmult(1,1,n,1,w[0].first))%mod;
}
if(i>0)mult*=x[w[i-1].first];
}
return ans;
}
int init(int N, int X[], int Y[]) {
//int init(int N, vector<int> X, vector<int> Y) {
n=N;
for(int i=1;i<=n;i++){
x[i]=X[i-1]; y[i]=Y[i-1];
xs.update(1,1,n,i,x[i]);
ys.update(1,1,n,i,y[i]);
}
return calc();
}
int updateX(int pos, int val) {
x[pos+1]=val;
xs.update(1,1,n,pos+1,val);
return calc();
}
int updateY(int pos, int val) {
y[pos+1]=val;
ys.update(1,1,n,pos+1,val);
return calc();
}
/*int main(){
init(3,{2,1,3},{3,4,1});
cout<<updateY(1,2)<<"\n";
return 0;
}*/
Compilation message
horses.cpp: In function 'int calc()':
horses.cpp:90:23: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
90 | for(int i=w.size()-1;i>=0;i--){
| ~~~~~~~~^~
horses.cpp:101:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
101 | return ans;
| ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:111:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
111 | xs.update(1,1,n,i,x[i]);
| ~~~^
horses.cpp:112:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
112 | ys.update(1,1,n,i,y[i]);
| ~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
445 ms |
38548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
