This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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; 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++) {
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |