Submission #1018423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018423		huutuan	Horses (IOI15_horses)	C++14	100 / 100	749 ms	64812 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct SegmentTree{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, 0);
   }
   void build(int k, int l, int r, int a[]){
      if (l==r){
         t[k]=a[l];
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid, a);
      build(k<<1|1, mid+1, r, a);
      t[k]=max(t[k<<1], t[k<<1|1]);
   }
   void update(int k, int l, int r, int pos, int val){
      if (l==r){
         t[k]=val;
         return;
      }
      int mid=(l+r)>>1;
      if (pos<=mid) update(k<<1, l, mid, pos, val);
      else update(k<<1|1, mid+1, r, pos, val);
      t[k]=max(t[k<<1], t[k<<1|1]);
   }
   int get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return 0;
      if (L<=l && r<=R) return t[k];
      int mid=(l+r)>>1;
      return max(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
   }
} st;

const int N=5e5+10, mod=1e9+7;

int binpow(int x, int y){
   int t=1;
   while (y){
      if (y&1) t=1ll*t*x%mod;
      x=1ll*x*x%mod;
      y>>=1;
   }
   return t;
}

set<int> pos;
int n, a[N], b[N];
int prod;

int solve(){
   vector<pair<long long, int>> v;
   int p=1;
   for (auto it=pos.rbegin(); it!=pos.rend(); ++it){
      v.emplace_back(0, *it);
      if (a[*it]>=(mod+p-1)/p) break;
      p*=a[*it];
   }
   reverse(v.begin(), v.end());
   int ans=prod;
   int cur=1;
   for (int i=0; i<(int)v.size(); ++i){
      if (i) ans=1ll*ans*binpow(a[v[i].second], mod-2)%mod;
      if (i) cur*=a[v[i].second];
      v[i].first=1ll*cur*st.get(1, 1, n, v[i].second, i+1==(int)v.size()?n:v[i+1].second-1);
   }
   auto opt=*max_element(v.begin(), v.end());
   return 1ll*ans*(opt.first%mod)%mod;
}

int32_t init(int32_t _N, int32_t X[], int32_t Y[]) {
   n=_N;
   st.init(n);
   prod=1;
   for (int i=1; i<=n; ++i){
      a[i]=X[i-1], b[i]=Y[i-1];
      if (a[i]!=1 || i==1) pos.insert(i);
      prod=1ll*prod*a[i]%mod;
   }
   st.build(1, 1, n, b);
   return solve();
}

int32_t updateX(int32_t i, int32_t val) {
   ++i;
   prod=1ll*prod*binpow(a[i], mod-2)%mod;
   prod=1ll*prod*val%mod;
   a[i]=val;
   pos.erase(i);
   if (a[i]!=1 || i==1) pos.insert(i);
   return solve();
}

int32_t updateY(int32_t i, int32_t val) {
   ++i;
   b[i]=val;
   st.update(1, 1, n, i, val);
   return solve();
}

Compilation message (stderr)

horses.cpp: In function 'int32_t init(int32_t, int32_t*, int32_t*)':
horses.cpp:90:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
   90 |    return solve();
      |           ~~~~~^~
horses.cpp: In function 'int32_t updateX(int32_t, int32_t)':
horses.cpp:100:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  100 |    return solve();
      |           ~~~~~^~
horses.cpp: In function 'int32_t updateY(int32_t, int32_t)':
horses.cpp:107:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  107 |    return solve();
      |           ~~~~~^~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23