제출 #857350

#제출 시각아이디문제언어결과실행 시간메모리
857350resting추월 (IOI23_overtaking)C++17
0 / 100
1 ms600 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; #define int long long vector<pair<int, int>> restriction; // if "starts after a", has to "end after b" yk int x, l; void init(int32_t L, int32_t N, std::vector<long long> T, std::vector<int32_t> W, int32_t X, int32_t M, std::vector<int32_t> S) { x = X; l = L; vector<vector<pair<int, int>>> restrictions(M);// yes vector<pair<int, int>> cur; for (int i = 0; i < N; i++) if (W[i] > X) cur.push_back({ T[i], W[i] - X }); sort(cur.begin(), cur.end()); for (int i = 0; i < M; i++) { vector<pair<int, int>> res; for (int j = 0; j < N; j++) res.push_back({ cur[j].first + cur[j].second * (T[i + 1] - T[i]), cur[j].second }); for (int j = 0; j < N - 1; j++) if (res[j].first > res[j + 1].first) res[j + 1].first = res[j].first; for (int j = 0; j < N; j++) restrictions[i].push_back({ cur[j].first, res[j].first }); //start, end swap(res, cur); sort(cur.begin(), cur.end()); } //restrictions i guess ["start after i has to end after j"] restriction = restrictions[0]; for (int i = 1; i < M; i++) { //transition from prev ??? //two pointers vector<pair<int, int>> nice; auto l1 = restriction, l2 = restrictions[i]; int p1 = restriction.size() - 1; int p2 = restrictions[i].size() - 1; int cur = 100000; while (p1 >= 0 && p2 >= 0) { if (p1 < 0) { nice.push_back(l2[p2]); cur = l2[p2].first; p2--; } else if (p2 < 0) { nice.push_back(l1[p1]); cur = l1[p1].first; p1--; } else if (l1[p1].second < l2[p2].second) { if (l1[p1].second >= l2[p2].first) { l2[p2].first = min(l2[p2].first, l1[p1].second); p1--; } else { nice.push_back(l2[p2]); cur = l2[p2].first; p2--; } } else { assert(l1[p1].second >= l2[p2].second); nice.push_back(l1[p1]); cur = l1[p1].first; p1--; } while (p1 >= 0 && l1[p1].first >= cur) p1--; if (p1 >= 0) l1[p1].second = min(l1[p1].second, cur - 1); while (p2 >= 0 && l2[p2].first >= cur) p2--; if (p2 >= 0) l2[p2].second = min(l2[p2].second, cur - 1); } swap(restriction, nice); } return; } long long arrival_time(long long Y) { auto yes = prev(upper_bound(restriction.begin(), restriction.end(), make_pair( Y, numeric_limits<long long>::max() ))); if (yes != restriction.end()) Y = max(Y, yes->second); return Y + x * l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...