Submission #545374

#	Time	Username	Problem	Language	Result	Execution time	Memory
545374		NemanjaSo2005	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	196 ms	149780 KiB

railroad

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N,res=0,uzeo[200005],uk,gde,tren;
queue<int> kol[200005];
struct slog{
   ll vred,org;
}kraj[200005],poc[200005];
bool cmp(slog a,slog b){
   return a.vred<b.vred;
}
ll bp(ll sta){
   ll dg=1,gg=N+1,ret=1e9,sred;
   while(dg<=gg){
      sred=dg+(gg-dg)/2;
      if(poc[sred].vred>sta){
         ret=sred;
         gg=sred-1;
      }
      else
         dg=sred+1;
   }
   return ret;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> u){
   N=s.size();
   for(int i=1;i<=5;i++){
      s.push_back(0);
      u.push_back(0);
   }
   for(int i=N;i>=1;i--){
      s[i]=s[i-1];
      u[i]=u[i-1];
   }
   for(int i=1;i<=N;i++){
      poc[i].org=kraj[i].org=i;
      poc[i].vred=s[i];
      kraj[i].vred=u[i];
   }
   sort(poc+1,poc+N+1,cmp);
   sort(kraj+1,kraj+N+1,cmp);
   for(int i=1;i<=N;i++){
      gde=bp(kraj[i].vred);
      if(gde==1e9){
         if(i!=N)
            res+=kraj[i].vred-poc[N].vred;
         gde=N;
      }
      if(i!=N)
         kol[gde].push(kraj[i].org);
   }
   uzeo[kraj[N].org]=1;
   uk=1;
   for(int i=N;i>=2;i--){
      //cout<<poc[i].org<<endl;
      uk-=uzeo[poc[i].org];
      uzeo[poc[i].org]^=1;
      uk+=uzeo[poc[i].org];
      while(kol[i].size()){
       //  cout<<kol[i].front()<<endl;
         uk-=uzeo[kol[i].front()];
         uzeo[kol[i].front()]^=1;
         uk+=uzeo[kol[i].front()];
         tren++;
         kol[i].pop();
      }
      tren--;
      if(tren>0){
         res+=tren*(poc[i].vred-poc[i-1].vred);
      }
     // cout<<i<<" "<<uk<<endl;
      if(tren==0 and uk==0 and i!=2){
         //cout<<"CYCLE "<<i<<" "<<poc[i].vred-poc[i-1].vred<<endl;
         res+=poc[i].vred-poc[i-1].vred;
      }
      if(i==2 and uk!=0)
         res+=poc[i].vred-poc[i-1].vred;
   }
   return res;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36