Submission #160272

#	Time	Username	Problem	Language	Result	Execution time	Memory
160272		davi_bart	Horses (IOI15_horses)	C++14	37 / 100	726 ms	33364 KiB

horses

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int dim=1<<19;
int left(int p){return 2*p+1;}
int right(int p){return left(p)+1;}
int parent(int p){return (p-1)/2;}
int N,Q;
vector<int> 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(int pos,int da,int a,int ini,int 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,int> crea_albero(int pos,int a,int b){
  if(a==b)return horses[pos];
  pair<ll,int> k=crea_albero(left(pos),a,(a+b)/2);
  pair<ll,int> 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(int pos,int val){
  horses[pos].first=val;
  for(int 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;
  }
}
int crea_albero_sol(int pos,int a,int b){
  if(a==b)return sol[pos]=a;
  int k=crea_albero_sol(left(pos),a,(a+b)/2);
  int 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(int i=0;i<N;i++){
    horses[i+dim-1].first=(ll)(X[i]);
  }
  crea_albero(0,0,dim-1);
  for(int i=0;i<N;i++){
    costo[i]=Y[i];
  }
  crea_albero_sol(0,0,dim-1);
  int best=sol[0];
  return (int)((costo[best]*prodotto(0,0,dim-1,0,best).first)%mod);
}
void update_sol(int pos){
  for(int i=parent(pos);i>=0;i=parent(i)){
    int k=sol[left(i)];
    int 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);
  int 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);
  int best=sol[0];
  return (int)((costo[best]*prodotto(0,0,dim-1,0,best).first)%mod);
}/*
int main(){
  //freopen("input.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(int i=0;i<N;i++)cin>>x[i];
  for(int i=0;i<N;i++)cin>>y[i];
  cout<<init(N,x,y)<<endl;
  int Q;
  cin>>Q;
  for(int 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;
}*/

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:49:29: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N,int* X,int* Y){
                             ^
horses.cpp:11:5: note: shadowed declaration is here
 int N,Q;
     ^

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