Submission #850322

#	Time	Username	Problem	Language	Result	Execution time	Memory
850322		NemanjaSo2005	Overtaking (IOI23_overtaking)	C++17	100 / 100	2205 ms	152884 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,M,L,X,niz[1005];;
struct bus{
    ll w,krece,stize;
    bool operator < (const bus &a) const{
        return krece<a.krece;
    }
} bpp;
bool cmp(bus a,bus b){
    return a.w>b.w;
}
struct slog{
    ll l,r,ans;
    const bool operator < (const slog &a) const{
      return l<a.l;
    }
} pp;
set<slog> S;
set<bus> busevi[1005];
pair<set<bus>,vector<bus>> resi(vector<bus> V,ll d){
   set<bus> A;
   vector<bus> B;
   if(V.size()==0)
     return {A,B};
   bpp.krece=bpp.stize=-1;
   A.insert(bpp);
   sort(V.begin(),V.end(),cmp);
   for(int i=0;i<V.size();i++){
      bpp.krece=V[i].krece;
      auto it=A.lower_bound(bpp);
      it--;
      V[i].stize=d*V[i].w+V[i].krece;
      if(V[i].stize<(*it).stize)
         V[i].stize=(*it).stize;
      else
         A.insert(V[i]);
      B.push_back(V[i]);
   }
   bpp.krece=bpp.stize=-1;
   A.erase(bpp);
   return {A,B};
}
ll arrival_time(ll Y);
void dodajint(slog x){
   if(S.size()==0){
      S.insert(x);
      return;
   }
   auto poc=S.upper_bound(x);
   if(poc!=S.begin())
      poc--;
   if((*poc).l>x.r){
      S.insert(x);
      return;
   }
   vector<slog> B,D;
   D.push_back(x);
   for(auto it=poc;it!=S.end();it++){
      slog t2,tren=*it;
      if(tren.l>x.r)
         break;
      if(tren.r<x.l)
         continue;
      if(tren.l>=x.l and tren.r<=x.r){
         B.push_back(tren);
         continue;
      }
      if(tren.l<x.l and tren.r>=x.l){
         t2=tren;
         B.push_back(t2);
         t2.r=x.l-1;
         D.push_back(t2);
      }
      if(tren.l<=x.r and tren.r>x.r){
         B.push_back(tren);
         tren.l=x.r+1;
         D.push_back(tren);
      }
   }
   for(int i=0;i<B.size();i++)
      S.erase(B[i]);
   for(int i=0;i<D.size();i++)
      S.insert(D[i]);
}
void init(int l,int n,vector<ll> t,vector<int> w,int x,int m,vector<int> s){
   N=n;
   L=l;
   M=m;
   X=x;
   for(int i=0;i<M;i++)
     niz[i]=s[i];
   vector<bus> V;
   for(int i=0;i<N;i++){
     if(w[i]<=X)
         continue;
     bpp.w=w[i];
     bpp.krece=t[i];
     bpp.stize=t[i];
     V.push_back(bpp);
   }
   for(int i=0;i+1<M;i++){
      for(int j=0;j<V.size();j++)
         V[j].krece=V[j].stize;
      auto odg=resi(V,niz[i+1]-niz[i]);
      busevi[i]=odg.first;
      V=odg.second;
   //   cout<<"BUSEVI "<<i<<endl;
    //  for(auto it=busevi[i].begin();it!=busevi[i].end();it++)
      //   cout<<(*it).krece<<" "<<(*it).stize<<" "<<(*it).w<<endl;
   }
   vector<slog> D;
   for(int i=M-2;i>=0;i--){
      //cout<<i<<endl;
      ll d=(niz[i+1]-niz[i]);
      for(auto it=busevi[i].begin();it!=busevi[i].end();it++){
         bpp=*it;
         slog tren;
         tren.l=bpp.krece+1;
         tren.r=bpp.stize-d*X;
         //cout<<tren.l<<" "<<tren.r<<" ans od "<<bpp.stize-niz[i+1]*X<<endl;
         tren.ans=arrival_time(bpp.stize-niz[i+1]*X);
         tren.l-=niz[i]*X;
         tren.r-=niz[i]*X;
         D.push_back(tren);
         //cout<<tren.l<<" "<<tren.r<<" "<<tren.ans<<endl;
      }
      for(int j=0;j<D.size();j++)
         dodajint(D[j]);
       //cout<<"SET:"<<endl;
      //for(auto it=S.begin();it!=S.end();it++)
       //  cout<<(*it).l<<" "<<(*it).r<<" "<<(*it).ans<<endl;
      D.clear();
   }
}
ll arrival_time(ll Y){
    if(S.size()==0)
        return Y+X*L;
    pp.l=Y;
    slog x;
    x.ans=-1;
    auto it=S.upper_bound(pp);
    if(it!=S.begin())
        it--;
    if((*it).l<=Y and (*it).r>=Y)
        return (*it).ans;
    return Y+X*L;
}

Compilation message (stderr)

overtaking.cpp: In function 'std::pair<std::set<bus>, std::vector<bus> > resi(std::vector<bus>, long long int)':
overtaking.cpp:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bus>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for(int i=0;i<V.size();i++){
      |                ~^~~~~~~~~
overtaking.cpp: In function 'void dodajint(slog)':
overtaking.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for(int i=0;i<B.size();i++)
      |                ~^~~~~~~~~
overtaking.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int i=0;i<D.size();i++)
      |                ~^~~~~~~~~
overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bus>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |       for(int j=0;j<V.size();j++)
      |                   ~^~~~~~~~~
overtaking.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |       for(int j=0;j<D.size();j++)
      |                   ~^~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:142:10: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  142 |     slog x;
      |          ^

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 35 / 35