Submission #850261

#	Time	Username	Problem	Language	Result	Execution time	Memory
850261		NemanjaSo2005	Overtaking (IOI23_overtaking)	C++17	65 / 100	3529 ms	63472 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;
};
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]);
   }
   return {A,B};
}
ll arrival_time(ll Y);
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(int j=0;j<V.size();j++)
         cout<<V[j].krece<<" "<<V[j].stize<<" "<<V[j].w<<endl;*/
   }
}
ll arrival_time(ll Y){
   for(int i=0;i+1<M;i++){
      //cout<<i<<" "<<Y<<endl;
      //cout<<niz[i+1]-niz[i]<<endl;
      if(busevi[i].size()==0){
         Y=Y+X*(niz[i+1]-niz[i]);
         continue;
      }
      bpp.krece=Y;
      auto it=busevi[i].lower_bound(bpp);
      if(it!=busevi[i].begin()){
         it--;
         Y=max(Y+X*(niz[i+1]-niz[i]),(*it).stize);
      }
      else
         Y=Y+X*(niz[i+1]-niz[i]);
   }
   return 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)
        ans=(*it).ans;
    if(ans!=-1)
        return 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:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bus>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for(int i=0;i<V.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:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bus>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |       for(int j=0;j<V.size();j++)
      |                   ~^~~~~~~~~

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