Submission #1053896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053896		Ahmed57	Overtaking (IOI23_overtaking)	C++17	0 / 100	0 ms	348 KiB

overtaking

#include "bits/stdc++.h"

using namespace std;
#define int long long
vector<array<int,4>> all;
void init(int32_t L, int32_t N,vector<long long> T,vector<int32_t> W, int32_t X, int32_t M,vector<int32_t>S){
    //cout<<"hhh"<<endl;
    vector<pair<int ,int>> v;
    for(int i = 0;i<N;i++){
        v.push_back({T[i],W[i]});
    }
    sort(v.begin(),v.end());
    vector<array<int,4>> rngs;
    int la = -1e18;
    for(int i = 0;i<v.size();i++){
        if(v[i].first!=la)rngs.push_back({la,v[i].first,la,v[i].first});
        la = v[i].first;
    }
    rngs.push_back({la,1000000000000000000,la,1000000000000000000});
    //cout<<"hhh"<<endl;
    for(int i = 0;i<M-1;i++){
        //cout<<"bb"<<endl;
        sort(v.begin(),v.end());
        sort(rngs.begin(),rngs.end());
        int la =-1e18 , it = 0;
        vector<pair<int,int>> nv;
        vector<array<int,4>> nrngs;
        int slow = -1e18;
        for(int j = 0;j<rngs.size();j++){
            while(it<v.size()&&v[it]<make_pair(rngs[j][2],(long long)X)){
                int sh = v[it].first+(S[i+1]-S[i])*v[it].second;
                sh = max(sh,slow);
                slow = max(slow,sh);
                nv.push_back({sh,v[it].second});
                it++;
            }
            int dist = (S[i+1]-S[i])*X;
            if(rngs[j][2]==rngs[j][3]){
                nrngs.push_back({rngs[j][0],rngs[j][1],max(slow,rngs[j][2]+dist),max(slow,rngs[j][2]+dist)});
                continue;
            }
            int L = rngs[j][2];
            int R = (slow-dist);
            R = min(R,rngs[j][3]);
            if(R>=L){
                nrngs.push_back({rngs[j][0],rngs[j][0]+(R-L),slow,slow});
            }
            R = max(R,rngs[j][2]);
            if(R<rngs[j][3]){
                nrngs.push_back({rngs[j][0]+(R-L),rngs[j][1],R+dist,rngs[j][3]+dist});
            }
        }
        while(it<v.size()){
            int sh = v[it].first+(S[i+1]-S[i])*v[it].second;
            sh = max(sh,slow);
            slow = max(slow,sh);
            nv.push_back({slow,v[it].second});
            it++;
        }
        v = nv;
        rngs = nrngs;
    }all = rngs;
}
long long arrival_time(long long Y){
    int l = 0 , r = all.size()-1 , ans = 0;
    while(l<=r){
        int mid = (l+r)/2;
        if(all[mid][0]<=Y){
            ans = mid;
            l = mid+1;
        }else r = mid-1;
    }
    if(all[ans][2]==all[ans][3])return all[ans][2];
    return all[ans][2]+(Y-all[ans][0]);
}
/*signed main(){
    init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});
    cout<<arrival_time(50);

}*/

Compilation message (stderr)

overtaking.cpp: In function 'void init(int32_t, int32_t, std::vector<long long int>, std::vector<int>, int32_t, int32_t, std::vector<int>)':
overtaking.cpp:15:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~
overtaking.cpp:29:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int j = 0;j<rngs.size();j++){
      |                       ~^~~~~~~~~~~~
overtaking.cpp:30:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             while(it<v.size()&&v[it]<make_pair(rngs[j][2],(long long)X)){
      |                   ~~^~~~~~~~~
overtaking.cpp:53:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while(it<v.size()){
      |               ~~^~~~~~~~~
overtaking.cpp:25:13: warning: unused variable 'la' [-Wunused-variable]
   25 |         int la =-1e18 , it = 0;
      |             ^~

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