#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define P push
#define I insert
#define F first
#define S second
typedef long long ll;
const ll mod=1e9+7;
const int maxn=500000;
int n;
ll segx[4*maxn],segy[4*maxn];
ll co[maxn],pr[maxn];
set<int> notone;
ll expo(ll x,ll y){
if(y==0)return 1;
if(y%2==1)return (x*expo((x*x)%mod,y/2))%mod;
else return expo(x*x,y/2);
}
void updx(ll a,ll b,int c,ll x,ll px,int y){
segx[c]=(segx[c]%mod*expo(px,mod-2)%mod)%mod;
segx[c]*=x;segx[c]%=mod;
if(a==b)return;
ll m=(a+b)/2;
if(y<=m)updx(a,m,2*c,x,px,y);
else updx(m+1,b,2*c+1,x,px,y);
}
ll findx(ll a,ll b,ll c,ll x,ll y){
if(a==x && b==y)return segx[c];
ll m=(a+b)/2;
if(y<=m)return findx(a,m,2*c,x,y);
if(x>=m+1)return findx(m+1,b,2*c+1,x,y);
return (findx(a,m,2*c,x,m)*findx(m+1,b,2*c+1,m+1,y))%mod;
}
void updy(ll a,ll b,int c,ll x,int y){
segy[c]=max(segy[c],x);
if(a==b)return;
ll m=(a+b)/2;
if(y<=m)updy(a,m,2*c,x,y);
else updy(m+1,b,2*c+1,x,y);
}
ll findy(ll a,ll b,ll c,ll x,ll y){
if(a==x && b==y)return segy[c];
ll m=(a+b)/2;
if(y<=m)return findy(a,m,2*c,x,y);
if(x>=m+1)return findy(m+1,b,2*c+1,x,y);
return max(findy(a,m,2*c,x,m),findy(m+1,b,2*c+1,m+1,y));
}
int func(){
auto itr=notone.end();itr--;
int last=*itr;itr--;
vector<pair<ll,ll> > v;
while(true){
if(v.size()>=80)break;
int cur=*itr;
if(cur+1!=last)v.PB(MP(last-1,findy(0,n-1,1,cur+1,last-1)));
if(cur==-1)break;
v.PB(MP(cur,pr[cur]));
last=cur;
itr--;
}
reverse(v.begin(),v.end());
int cmax=0;
ll mul=co[v[0].F];
for(int i=1;i<v.size();i++){
if(mul*v[i].S>v[cmax].S){
cmax=i;
mul=1;
}
mul*=co[v[cmax].F];
}
ll ans=v[cmax].S;
if(v[cmax].F>0)ans*=findx(0,n-1,1,0,v[cmax].F-1);
return ans;
}
int init(int N, int X[], int Y[]) {
n=N;
memset(segx,1,sizeof(segx));
memset(segy,0,sizeof(segy));
for(int i=0;i<n;i++){
co[i]=X[i];
pr[i]=Y[i];
updy(0,n-1,1,Y[i],i);
updx(0,n-1,1,X[i],1,i);
}
notone.I(-1);notone.I(n);
for(int i=0;i<n;i++)if(X[i]!=1)notone.I(i);
return 0;
}
int updateX(int pos, int val) {
updx(0,n-1,1,val,co[pos],pos);
co[pos]=val;
if(val==1)notone.erase(pos);
else notone.I(pos);
return func();
}
int updateY(int pos, int val) {
updy(0,n-1,1,val,pos);
pr[pos]=val;
return func();
}
Compilation message
horses.cpp: In function 'int func()':
horses.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=1;i<v.size();i++){
| ~^~~~~~~~~
horses.cpp:76:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
76 | return ans;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
31572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
31592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1568 ms |
69876 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
31572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
31536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
