Submission #1215747

#TimeUsernameProblemLanguageResultExecution timeMemory
1215747trimkusOvertaking (IOI23_overtaking)C++20
100 / 100
1449 ms105444 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; using ll = long long; int N, L; vector<int> W, S; int X, M; vector<ll> T; ll expected[1001][1001]; vector<int> tot_ord[1001]; int pos[1001][1001]; map<ll, ll> mp; ll shift = 0; ll query(ll x) { x += shift; auto it = mp.upper_bound(x); if (it != begin(mp)) x = max(x, prev(it)->second); return x; } void merge(ll x, ll y) { x += shift; auto it = mp.upper_bound(x); if (it != begin(mp) && prev(it)->second >= y) return; mp[x] = y; it = mp.find(x); while (next(it) != mp.end() && next(it)->second <= y) mp.erase(next(it)); } void init(int _L, int _N, std::vector<long long> _T, std::vector<int> _W, int _X, int _M, std::vector<int> _S) { L = _L; M = _M; N = _N; T = _T; W = _W; X = _X; S = _S; // W.push_back(X); // vector<vector<ll>> exp(N, vector<ll>(M)); vector<int> ord(N); iota(begin(ord), end(ord), 0); for (int i = 0; i < N; ++i) { expected[i][0] = T[i]; } for (int j = 1; j < M; ++j) { sort(begin(ord), end(ord), [&](int x, int y){ if (expected[x][j - 1] != expected[y][j - 1]) return expected[x][j - 1] < expected[y][j - 1]; return W[x] < W[y]; }); tot_ord[j - 1] = ord; ll tim = -1; for (int it = 0; it < N; ++it) { int i = ord[it]; pos[j - 1][i] = it; // cerr << W[i] << " "; expected[i][j] = expected[i][j - 1] + 1LL * W[i] * (S[j] - S[j - 1]); expected[i][j] = max(tim, expected[i][j]); tim = max(expected[i][j], tim); } // cerr << endl; if (j == M - 1) { sort(begin(ord), end(ord), [&](int x, int y){ if (expected[x][j - 1] != expected[y][j - 1]) return expected[x][j - 1] < expected[y][j - 1]; return W[x] < W[y]; }); tot_ord[j] = ord; for (int it = 0; it < N; ++it) { int i = ord[it]; pos[j][i] = it; } } } // for (int i = 0; i < M; ++i) { // for (int j = 0; j < N; ++j) { // cerr << expected[j][i] << " "; // } // cerr << "\n"; // } // cerr << "\nDone!\n"; for (int i = M - 2; i >= 0; --i) { vector<array<ll, 2>> a; for (int it = 0; it < N; ++it) { // int i1 = tot_ord[i - 1][it]; // int i2 = tot_ord[i][it]; // int v = tot_ord[i - 1][it]; ll e1 = expected[it][i]; ll e2 = expected[it][i + 1]; // cerr << e1 << " " << e2 << "\n"; a.push_back({e1, query(e2)}); } shift += 1LL * X * (S[i + 1] - S[i]); for (auto& [x, y] : a) { merge(x + 1, y); } // for (auto& [x, y] : mp) { // cerr << x << " " << y << "\n"; // } // cerr << "\n"; } } long long arrival_time(long long Y) { return query(Y); }
#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...