Submission #848386

#TimeUsernameProblemLanguageResultExecution timeMemory
848386math_rabbit_1028Overtaking (IOI23_overtaking)C++17
29 / 100
120 ms169692 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; int l, n, x, m; vector<ll> t; vector<int> w, s; ll est[1010][1010], arr[1010][1010]; pll range[1010][1010]; struct seg { int sz; vector<ll> vals; ll tree[4040], lazy[4040]; void init(int v, int st, int ed) { if (st == ed) { tree[v] = -1; lazy[v] = -1; return; } int mid = (st + ed) / 2; init(2 * v, st, mid); init(2 * v + 1, mid + 1, ed); tree[v] = max(tree[2 * v], tree[2 * v + 1]); lazy[v] = -1; } void propagate(int v, int st, int ed) { tree[v] = max(tree[v], lazy[v]); if (st != ed) { lazy[2 * v] = max(lazy[2 * v], lazy[v]); lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]); } } void update(int v, int st, int ed, int lt, int rt, ll val) { propagate(v, st, ed); if (lt > ed || rt < st) return; if (lt <= st && ed <= rt) { lazy[v] = max(lazy[v], val); propagate(v, st, ed); return; } int mid = (st + ed) / 2; update(2 * v, st, mid, lt, rt, val); update(2 * v + 1, mid + 1, ed, lt, rt, val); tree[v] = max(tree[2 * v], tree[2 * v + 1]); } ll get(int v, int st, int ed, int idx) { propagate(v, st, ed); if (st > idx || ed < idx) return -1; if (st == idx && ed == idx) return tree[v]; int mid = (st + ed) / 2; return max(get(2 * v, st, mid, idx), get(2 * v + 1, mid + 1, ed, idx)); } } sg[1010]; void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) { l = L; n = N; t = T; w = W; x = X; m = M; s = S; for (int i = 0; i < n; i++) arr[0][i] = t[i]; for (int j = 1; j < m; j++) { for (int i = 0; i < n; i++) est[j][i] = arr[j - 1][i] + (ll)w[i] * (s[j] - s[j - 1]); vector<pll> tlist; for (int i = 0; i < n; i++) tlist.push_back({arr[j - 1][i], i}); sort(tlist.begin(), tlist.end()); ll last = 0, p = 0; for (int i = 0; i < n; i++) { while (tlist[p].first < tlist[i].first) { last = max(last, est[j][tlist[p].second]); p++; } arr[j][tlist[i].second] = max(last, est[j][tlist[i].second]); } } for (int j = 0; j < m - 1; j++) { for (int i = 0; i < n; i++) { if (w[i] > x) { range[j][i] = {arr[j][i] + 1, arr[j][i] + (ll)(w[i] - x) * (s[j + 1] - s[j])}; sg[j].vals.push_back(range[j][i].first); sg[j].vals.push_back(range[j][i].second); } } sort(sg[j].vals.begin(), sg[j].vals.end()); sg[j].vals.erase(unique(sg[j].vals.begin(), sg[j].vals.end()), sg[j].vals.end()); sg[j].sz = sg[j].vals.size(); sg[j].init(1, 0, sg[j].sz); for (int i = 0; i < n; i++) { if (w[i] > x) { int s = lower_bound(sg[j].vals.begin(), sg[j].vals.end(), range[j][i].first) - sg[j].vals.begin() + 1; int e = lower_bound(sg[j].vals.begin(), sg[j].vals.end(), range[j][i].second) - sg[j].vals.begin() + 1; sg[j].update(1, 0, sg[j].sz, s, e - 1, arr[j + 1][i]); } } } return; } ll arrival_time(ll Y) { ll y = Y; for (int j = 0; j < m - 1; j++) { int idx = upper_bound(sg[j].vals.begin(), sg[j].vals.end(), y) - sg[j].vals.begin(); ll next = sg[j].get(1, 0, sg[j].sz, idx); if (next >= 0) y = next; else y = y + (ll)x * (s[j + 1] - s[j]); //cout << y << "\n"; } return 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...