Submission #1213502

#TimeUsernameProblemLanguageResultExecution timeMemory
1213502NeltOvertaking (IOI23_overtaking)C++17
0 / 100
0 ms836 KiB
#include "overtaking.h" #include <bits/stdc++.h> #pragma GCC optimize("O3") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define endl "\n" using namespace std; using namespace __gnu_pbds; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T, typename key = less<T>> using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>; const ll N = 1005, inf = 9e18; pair<ll, ll> mx[N][N]; vector<pair<ll, ll>> tmp[N]; set<array<ll, 3>> st; ll dp[N][N]; ll t[N][N]; ll v[N], s[N]; ll n, m, X; void add(ll l, ll r, ll x) { set<array<ll, 3>>::iterator it; while ((it = st.lower_bound({l, -1, -1})) != st.end() and it->operator[](1) <= r) st.erase(it); if (it != st.end() and it->operator[](0) <= r) { auto [l1, r1, x1] = *it; st.erase(it); st.insert({r + 1, r1, x1}); } it = st.lower_bound({l, -1, -1}); if (it != st.begin()) { it--; if (it->operator[](1) >= l) { auto [l1, r1, x1] = *it; st.erase(it); st.insert({l1, l - 1, x1}); } } st.insert({l, r, x}); } ll getpoint(ll x) { auto it = st.upper_bound({x, inf, inf}); if (it != st.begin()) { it--; if (it->operator[](1) >= x) return it->operator[](2); } return -1; } void init(int L, int N, std::vector<long long> T, std::vector<int> W, int x_, int M, std::vector<int> S) { X = x_; n = N, m = M; for (ll i = 0; i < n; i++) t[i][0] = T[i]; for (ll i = 0; i < n; i++) v[i] = W[i]; v[n] = X; for (ll i = 0; i < m; i++) s[i] = S[i]; for (ll i = 0; i < n; i++) tmp[0].push_back(make_pair(t[i][0], i)); sort(tmp[0].begin(), tmp[0].end()); for (ll i = 1; i < m; i++) { for (ll x = 0; x < n; x++) { ll j = tmp[i - 1][x].second; t[j][i] = t[j][i - 1] + v[j] * (s[i] - s[i - 1]); mx[i][x] = max(x > 0 ? mx[i][x - 1] : make_pair(0ll, 0ll), make_pair(t[j][i], j)); ll pos = 0ll + lower_bound(tmp[i - 1].begin(), tmp[i - 1].end(), make_pair(t[j][i - 1], -1ll)) - tmp[i - 1].begin() - 1; if (pos >= 0) t[j][i] = max(t[j][i], mx[i][pos].first); } for (ll j = 0; j < n; j++) tmp[i].push_back(make_pair(t[j][i], j)); sort(tmp[i].begin(), tmp[i].end()); } for (ll i = m - 1; i >= 0; i--) { for (ll j = 0, pt, last, pos; j < n; j++) { pt = getpoint(t[i][j]); if (pt == -1) dp[i][j] = t[i][j] + (L - s[i]) * X; else { last = t[i][j] + (s[pt - 1] - s[i]) * X; pos = lower_bound(tmp[pt - 1].begin(), tmp[pt - 1].end(), make_pair(last, -1ll)) - tmp[pt - 1].begin(); if (pos >= 0) dp[i][j] = dp[pt][mx[pt][pos].second]; else assert(0 == 1); } } if (i) for (ll j = 0; j < n; j++) add(t[i - 1][j] - s[i - 1] * X + 1, t[i][j] - s[i] * X, i); } for (auto [l, r, x] : st) cout << l << " " << r << " " << x << endl; } long long arrival_time(long long cur) { // ll pt = getpoint(cur); // if (pt == -1) // return cur + s[m - 1] * X; // ll last = cur + s[pt - 1] * X; // ll pos = lower_bound(tmp[pt - 1].begin(), tmp[pt - 1].end(), make_pair(last, -1ll)) - tmp[pt - 1].begin(); // if (pos >= 0) // return dp[pt][mx[pt][pos].second]; // assert(0); for (ll i = 1; i < m; i++) { ll pos = lower_bound(tmp[i - 1].begin(), tmp[i - 1].end(), make_pair(cur, -1ll)) - tmp[i - 1].begin() - 1; cur += v[n] * (s[i] - s[i - 1]); if (pos >= 0) cur = max(cur, mx[i][pos].first); } return cur; }
#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...