이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 2e18;
ll g;
set<pair<ll, ll>> ans;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
g = (ll) L * X;
vector<pair<ll, int>> lines;
for(int i = 0; i < N; i++) {
if(W[i] > X) {
lines.push_back({T[i], W[i] - X});
}
}
sort(lines.begin(), lines.end());
lines.resize(unique(lines.begin(), lines.end()) - lines.begin());
vector<vector<ll>> t(lines.size(), vector<ll>(M));
vector<vector<bool>> inter(lines.size(), vector<bool>(M));
vector<int> o(lines.size());
for(int i = 0; i < lines.size(); i++) t[i][0] = lines[i].first, o[i] = i;
for(int i = 0; i < M - 1; i++) {
for(int j = 0; j < lines.size(); j++) {
t[j][i + 1] = (ll)(S[i + 1] - S[i]) * lines[j].second + t[j][i];
}
sort(o.begin(), o.end(), [&] (int a, int b) { return t[a][i] < t[b][i]; });
ll mx = 0;
int j = 0;
for(int k : o) {
while(t[o[j]][i] < t[k][i]) mx = max(mx, t[o[j++]][i + 1]);
if(t[k][i + 1] <= mx) {
inter[k][i + 1] = true;
t[k][i + 1] = mx;
}
}
}
ans.insert({0, 0});
set<pair<ll, ll>> last;
for(int i = M - 2; i >= 0; i--) {
last = ans;
sort(o.begin(), o.end(), [&] (int a, int b) { return t[a][i] < t[b][i]; });
for(int j : o) {
if(!inter[j][i + 1]) {
pair<ll, ll> p = {t[j][i] + 1, t[j][i + 1]};
auto o = *prev(ans.lower_bound(make_pair(t[j][i + 1], INF)));
if(p.second < o.second) {
if(o.first < p.first) continue;
p.second = o.second;
}
ans.insert(p);
while(*prev(ans.lower_bound(make_pair(t[j][i + 1], INF))) != p) {
ans.erase(*prev(ans.lower_bound(make_pair(t[j][i + 1], INF))));
}
}
}
}
}
ll arrival_time(ll Y) {
return max(Y, (*prev(ans.lower_bound(make_pair(Y, INF)))).second) + g;
}
컴파일 시 표준 에러 (stderr) 메시지
overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i = 0; i < lines.size(); i++) t[i][0] = lines[i].first, o[i] = i;
| ~~^~~~~~~~~~~~~~
overtaking.cpp:24:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int j = 0; j < lines.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... |