Submission #1122042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122042		epicci23	Horses (IOI15_horses)	C++17	100 / 100	1146 ms	63980 KiB

horses

#include "bits/stdc++.h"
#include "horses.h"
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
 
const ll N = 5e5 + 5;
const ll INF = 1e18 + 5;
const ll MOD = 1e9 + 7;
 
inline ll add(ll a,ll b){
  if(a+b>=MOD) return a+b-MOD;
  return a+b;
}
 
inline ll mult(ll a,ll b){
  if(a*b>=MOD) return a*b%MOD;
  return a*b;
}
 
inline ll fast(ll a,ll b,ll res=1){
  for(;b;a=mult(a,a),b>>=1) if(b&1) res=mult(res,a);
  return res;
}
 
inline ll inv(ll a){
  return fast(a,MOD-2);
}
 
struct SegT{
  vector<ll> seg;
  ll n,def;
  SegT(ll _n,ll _def){
  	n=_n,def=_def;
    seg.assign(4*n+5,def);
  }
  void upd(ll rt,ll l,ll r,ll ind,ll u){
  	if(r<ind || l>ind) return;
  	if(l==r){
  	  seg[rt]=u;
  	  return;
  	}
    ll mid=(l+r)/2;
    upd(rt*2,l,mid,ind,u),upd(rt*2+1,mid+1,r,ind,u);
    seg[rt]=max(seg[rt*2],seg[rt*2+1]);
  }
  ll query(ll rt,ll l,ll r,ll gl,ll gr){
    if(r<gl || l>gr) return def;
    if(l>=gl && r<=gr) return seg[rt];
    ll mid=(l+r)/2;
    return max(query(rt*2,l,mid,gl,gr),query(rt*2+1,mid+1,r,gl,gr));
  }
};
 
ll fw[N],n;
set<ll> s;
SegT T(N,-INF);
array<ll,2> ar[N];
 
inline void upd(ll c,ll u){
  for(;c<N;c+=c&-c) fw[c]=mult(fw[c],u);
}
 
inline ll query(ll c,ll res=1){
  for(;c;c-=c&-c) res=mult(res,fw[c]);
  return res;
}
 
inline ll find_ans(){
  vector<ll> v;
  set<ll>::reverse_iterator it = s.rbegin();
  ll ekle = 100;
  while(ekle--){
  	if(it==s.rend()) break;
  	v.push_back(*it);
  	it++;
  	if(it==s.rend()) break;
  }
  reverse(all(v));
  ll m = sz(v);
  vector<ll> g;
  for(ll i = 0; i < m; i++) g.push_back(T.query(1,1,n,v[i],(i+1==m ? n+1 : v[i+1])-1));
  ll best = 0 , as = 1;
  for(ll i = 1 ; i < m ;i++){
  	ll ind = v[i];
  	as *= ar[ind][0];
  	if(as >= (g[best]+g[i]-1)/g[i]){
  	  best = i;
  	  as = 1;
  	}
  }
  return mult(g[best],query(v[best]));
}
 
int init(int nn, int X[], int Y[]){
  n = nn;
  for(ll i = 1; i <= n ; i++) ar[i][0] = X[i-1], ar[i][1] = Y[i-1];
  fill(fw,fw+N,1);
  for(ll i = 1 ; i <= n ; i++) upd(i,ar[i][0]);
  s.insert(1);
  for(ll i=2;i<=n;i++) if(ar[i][0] >= 2) s.insert(i);
  for(ll i=1;i<=n;i++) T.upd(1,1,n,i,ar[i][1]);
 
  return (int)find_ans();
}
 
int updateX(int pos, int val){
  pos++;
  if(pos >= 2) s.erase(pos);
  upd(pos,inv(ar[pos][0]));
  
  ar[pos][0] = val;
  if(pos >= 2 && val >= 2) s.insert(pos);  
  upd(pos,val);
 
  return (int)find_ans();
}
 
int updateY(int pos, int val){
  pos++;
  ar[(ll)pos][1] = (ll) val;
  T.upd(1,1,n,(ll)pos,ar[pos][1]);
  return (int)find_ans();
}
 
/*void _(){
  cin >> n; 
  for(ll i = 1; i <= n ; i++) cin >> ar[i][0] >> ar[i][1];
  fill(fw,fw+N,1);
  for(ll i = 1 ; i <= n ; i++) upd(i,ar[i][0]);
  for(ll i=1;i<=n;i++) if(ar[i][0] >= 2) s.insert(i);
  for(ll i=1;i<=n;i++) T.upd(1,1,n,i,ar[i][1]);
 
}
 
int32_t main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll tc=1;//cin >> tc;
  while(tc--) _();
}*/

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