| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1085552 | 2024-09-08T11:59:06 Z | 4QT0R | Horses (IOI15_horses) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
// #include "horses.h"
using namespace std;
#define ll long long
#define ld long double
struct node{
ld sum;
ld max_pref;
ll ind;
};
const ll mod=1e9+7;
const ll base=1<<19;
node max_tree[2*base];
ll xprod[2*base];
ll cost[base+1];
ll fast_pow(ll a, ll b){
if (b==1)return a;
ll cur=fast_pow(a,b/2);
cur=(cur*cur)%mod;
if (b&1)cur=(cur*a)%mod;
return cur;
}
void start(int v){
if (v>=base){
if (!xprod[v])xprod[v]=1;
if (!cost[v-base])cost[v-base]=1;
return;
}
start(2*v);
start(2*v+1);
xprod[v]=(xprod[2*v]*xprod[2*v+1])%mod;
max_tree[v]=max_tree[2*v];
if (max_tree[v].sum+max_tree[2*v+1].max_pref>max_tree[v].max_pref){
max_tree[v].max_pref=max_tree[v].sum+max_tree[2*v+1].max_pref;
max_tree[v].ind=max_tree[2*v+1].ind;
}
max_tree[v].sum+=max_tree[2*v+1].sum;
}
void mult(ll &a, ll b){
a=(a*b)%mod;
}
ll ans(int v){
ll odp=cost[v];
v+=base+1;
while(v>1){
if (v&1)mult(odp,xprod[v-1]);
v>>=1;
}
return odp;
}
int init(int n, int x[], int y[]){
for (int i = 1; i<=n; i++){
cost[i]=y[i-1];
xprod[i+base]=x[i-1];
max_tree[i+base].sum=logl(x[i-1])+logl(y[i-1])-logl(i==1?1:y[i-2]);
max_tree[i+base].max_pref=max_tree[i+base].sum;
max_tree[i+base].ind=i;
}
start(1);
return ans(max_tree[1].ind);
}
int updateX(int pos, int val){
pos++;
int v=pos+base;
xprod[v]=val;
max_tree[v].sum=logl(val)+logl(cost[pos])-logl(cost[pos-1]);
max_tree[v].max_pref=max_tree[v].sum;
v>>=1;
while(v){
xprod[v]=xprod[2*v];
mult(xprod[v],xprod[2*v+1]);
max_tree[v]=max_tree[2*v];
if (max_tree[v].sum+max_tree[2*v+1].max_pref>max_tree[v].max_pref){
max_tree[v].max_pref=max_tree[v].sum+max_tree[2*v+1].max_pref;
max_tree[v].ind=max_tree[2*v+1].ind;
}
max_tree[v].sum+=max_tree[2*v+1].sum;
v>>=1;
}
return ans(max_tree[1].ind);
}
int updateY(int pos, int val){
pos++;
int v=pos+base;
int v2=pos+1+base;
cost[pos]=val;
max_tree[v].sum=logl(xprod[v])+logl(cost[pos])-logl(cost[pos-1]);
max_tree[v].max_pref=max_tree[v].sum;
v>>=1;
max_tree[v2].sum=logl(xprod[v2])+logl(cost[pos+1])-logl(cost[pos]);
max_tree[v2].max_pref=max_tree[v2].sum;
v2>>=1;
while(v){
max_tree[v]=max_tree[2*v];
if (max_tree[v].sum+max_tree[2*v+1].max_pref>max_tree[v].max_pref){
max_tree[v].max_pref=max_tree[v].sum+max_tree[2*v+1].max_pref;
max_tree[v].ind=max_tree[2*v+1].ind;
}
max_tree[v].sum+=max_tree[2*v+1].sum;
v>>=1;
max_tree[v2]=max_tree[2*v2];
if (max_tree[v2].sum+max_tree[2*v2+1].max_pref>max_tree[v2].max_pref){
max_tree[v2].max_pref=max_tree[v2].sum+max_tree[2*v2+1].max_pref;
max_tree[v2].ind=max_tree[2*v2+1].ind;
}
max_tree[v2].sum+=max_tree[2*v2+1].sum;
v2>>=1;
}
return ans(max_tree[1].ind);
}
int wejx[1003];
int wejy[1003];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i<n; i++)cin >> wejx[i];
for (int i = 0; i<n; i++)cin >> wejy[i];
cout << init(n,wejx,wejy) << '\n';
}