Submission #160275

#	Time	Username	Problem	Language	Result	Execution time	Memory
160275		davi_bart	Horses (IOI15_horses)	C++14	37 / 100	861 ms	34296 KiB

horses

// #pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll dim=1<<19;
ll left(ll p){return 2*p+1;}
ll right(ll p){return left(p)+1;}
ll parent(ll p){return (p-1)/2;}
vector<ll> sol((1<<20)-1);//indice massimo
vector<ll> costo(1<<19);
vector<pair<ll,bool> > horses((1<<20)-1,{1,0});
pair<ll,bool> prodotto(ll pos,ll da,ll a,ll ini,ll fin){
  if(a<ini || da>fin)return {1,0};
  if(da>=ini && a<=fin)return horses[pos];
  pair<ll,bool> k=prodotto(left(pos),da,(a+da)/2,ini,fin);
  pair<ll,bool> k1=prodotto(right(pos),(a+da)/2+1,a,ini,fin);
  pair<ll,bool> g={0,0};
  if(k.second || k1.second || k.first*k1.first>=mod)g.second=1;
  g.first=(k.first*k1.first)%mod;
  return g;
}
pair<ll,ll> crea_albero(ll pos,ll a,ll b){
  if(a==b)return horses[pos];
  pair<ll,ll> k=crea_albero(left(pos),a,(a+b)/2);
  pair<ll,ll> k1=crea_albero(right(pos),(a+b)/2+1,b);
  if(k.second|| k1.second || k.first*k.second>=mod)horses[pos].second=1;
  horses[pos].first=(k.first*k1.first)%mod;
  return horses[pos];
}
void update_cavalli(ll pos,ll val){
  horses[pos].first=val;
  for(ll i=parent(pos);i>=0;i=parent(i)){
    if(horses[left(i)].second || horses[right(i)].second || horses[left(i)].first*horses[right(i)].first>=mod)horses[i].second=1;
    horses[i].first=(horses[left(i)].first*horses[right(i)].first)%mod;
    if(i==0)break;
  }
}
ll crea_albero_sol(ll pos,ll a,ll b){
  if(a==b)return sol[pos]=a;
  ll k=crea_albero_sol(left(pos),a,(a+b)/2);
  ll k1=crea_albero_sol(right(pos),(a+b)/2+1,b);
  pair<ll,bool> prod=prodotto(0,0,dim-1,k+1,k1);
  if(prod.second==1 || prod.first*costo[k1]>costo[k])return sol[pos]=k1;
  return sol[pos]=k;
}
int init(int N,int* X,int* Y){
  for(ll i=0;i<N;i++){
    horses[i+dim-1].first=(ll)(X[i]);
  }
  crea_albero(0,0,dim-1);
  for(ll i=0;i<N;i++){
    costo[i]=Y[i];
  }
  crea_albero_sol(0,0,dim-1);
  ll best=sol[0];
  return (int)((costo[best]*prodotto(0,0,dim-1,0,best).first)%mod);
}
void update_sol(ll pos){
  for(ll i=parent(pos);i>=0;i=parent(i)){
    ll k=sol[left(i)];
    ll k1=sol[right(i)];
    pair<ll,bool> prod=prodotto(0,0,dim-1,k+1,k1);
    if(prod.second==1 || prod.first*costo[k1]>costo[k])sol[i]=k1;
    else sol[i]=k;
    if(i==0)break;
  }
}
int updateX(int pos,int val){
  update_cavalli(pos+dim-1,val);
  update_sol(pos+dim-1);
  ll best=sol[0];
  return (int)((costo[best]*prodotto(0,0,dim-1,0,best).first)%mod);
}
int updateY(int pos,int val){
  costo[pos]=(ll)(val);
  update_sol(pos+dim-1);
  ll best=sol[0];
  return (int)((costo[best]*prodotto(0,0,dim-1,0,best).first)%mod);
}
// int main(){
//   freopen("input1.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
//   //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//   int N;
//   cin>>N;
//   int x[N],y[N];
//   for(ll i=0;i<N;i++)cin>>x[i];
//   for(ll i=0;i<N;i++)cin>>y[i];
//   cout<<init(N,x,y)<<endl;
//   int Q;
//   cin>>Q;
//   for(ll i=0;i<Q;i++){
//     int a,b,c;
//     cin>>a>>b>>c;
//     if(a==1)cout<<updateX(b,c)<<endl;
//     else cout<<updateY(b,c)<<endl;
//   }
//   return 0;
// }

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