Submission #848492

#	Time	Username	Problem	Language	Result	Execution time	Memory
848492		Rifal	Overtaking (IOI23_overtaking)	C++17	65 / 100	3540 ms	19028 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
const int Max = 1e3 + 5;
vector<long long> sta;
vector<pair<long long, long long>> bus;
vector<long long> v[Max], Mx[Max];
long long n, m, x;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    n = N, m = M; x = X;
    for(int i = 0; i < M; i++) sta.push_back(S[i]);
    for(int i = 0; i < N; i++) bus.push_back({T[i],W[i]});
    bus.push_back({-1,X});
    int siz = bus.size();
    long long cur[siz-1];
    for(int i = 0; i < siz-1; i++) {
        cur[i] = bus[i].first;
    }
    for(int i = 1; i < m; i++) {
        priority_queue<pair<pair<long long, long long>,int>, vector<pair<pair<long long,long long>,int>>, greater<pair<pair<long long, long long>,int>>> pq;
        pair<long long, long long> mx = {-1,-1};
        for(int j = 0; j < siz-1; j++) {
        //    cout << cur[j] << ' ' << bus[j].second << ' ' << sta[i] << ' ' << sta[i-1] << ' ' << j << endl;
            pq.push({{cur[j],cur[j] + bus[j].second * (sta[i]-sta[i-1])},j});
        }
        vector<long long> exp;
        while(!pq.empty()) {
            pair<pair<long long, long long>,int> tp = pq.top(); pq.pop();
            v[i].push_back(tp.first.first); exp.push_back(tp.first.second);
            if(mx.first < tp.first.second) {
                mx.first = tp.first.second;
                mx.second = tp.first.first;
            }
            if(mx.second == tp.first.first) {
                cur[tp.second] = tp.first.second;
            }
            else {
                cur[tp.second] = mx.first;
            }
 
        }
        long long mx2 = 0;
        for(int j = 0; j < exp.size(); j++) {
            mx2 = max(mx2,exp[j]);
            Mx[i].push_back(mx2);
        }
    }
}
 
long long arrival_time(long long Y)
{
    long long now = Y;
    for(int i = 1; i < m; i++) {
     /*   cout << "KKKKKKKKKKKKKKKK" << endl;
        for(int j = 0; j < v[i].size(); j++)  {
            cout << v[i][j] << ' ';
        }cout << endl;
        for(int j = 0; j < Mx[i].size(); j++)  {
            cout << Mx[i][j] << ' ';
        }cout << endl;
        cout << "KKKKKKKKKKKKK" << endl;*/
        int j = lower_bound(v[i].begin(),v[i].end(),now)-v[i].begin();
        if(j == 0) {
         ///   cout << '1' << ' ' << now << endl;
            now += x * (sta[i]-sta[i-1]);
        }
        else {
         ///   cout << '2' << ' ' << now << ' ' << Mx[i][j-1] << endl;
            now = max(now+x * (sta[i]-sta[i-1]),Mx[i][j-1]);
        }
 
    }
    return now;
}
/*
6 4 10 4 2
20 10 40 0
5 20 20 30
0 1 3 6
0
50*/

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int j = 0; j < exp.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