Submission #1227038

#TimeUsernameProblemLanguageResultExecution timeMemory
1227038dizzy_groovyTrain (APIO24_train)C++20
40 / 100
547 ms155948 KiB
#include "train.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = 1e15; struct PersSegTree{ struct Node{ Node *left; Node *right; ll l, r; ll su; Node (ll x, ll ind) { su = x; l = ind; r = ind + 1; left = nullptr; right = nullptr; } Node (Node *le, Node *ri) { left = le; right = ri; l = le->l; r = ri->r; su = le->su + ri->su; } }; vector<Node*> trs; Node* build(ll l, ll r) { if (r - l == 1) { return new Node(0ll, l); } ll m = (l + r) / 2; return new Node(build(l, m), build(m, r)); } Node* upd(ll ind, ll x, Node* tr) { if (tr->l > ind || ind >= tr->r) { return tr; } if (tr->r - tr->l == 1) { return new Node(tr->su + x, ind); } return new Node(upd(ind, x, tr->left), upd(ind, x, tr->right)); } ll update(ll i, ll ind, ll x) { trs.push_back(upd(ind, x, trs[i])); return trs.size() - 1; } ll get(ll l, ll r, Node *tr) { if (tr->r <= l || tr->l >= r) return 0ll; if (l <= tr->l && tr->r <= r) return tr->su; return get(l, r, tr->left) + get(l, r, tr->right); } ll get_ans(ll l, ll r, ll ind) { return get(l, r, trs[trs.size() - ind - 1]); } ll get2(Node* l, Node* r, ll ansl, ll ansr, ll w) { if (l->r - l->l == 1) { return l->l; } if (ansl + l->left->su * w < ansr + r->left->su * w) { ansl += l->left->su * w; ansr += r->left->su * w; return get2(l->right, r->right, ansl, ansr, w); } return get2(l->left, r->left, ansl, ansr, w); } ll get_ans2(ll indl, ll indr, ll ansl, ll ansr, ll w) { return get2(trs[trs.size() - indl - 1], trs[trs.size() - indr - 1], ansl, ansr, w); } PersSegTree(ll n) { trs.push_back(build(0ll, n)); } }; inline ll f(ll l, ll r, PersSegTree &tr, vector<pair<ll, ll>> &tmp2) { /*ll cnt = 0; for (auto &i : tmp2) { if (i.first > l && i.second < r) cnt++; } return cnt;*/ return tr.get_ans(0ll, r + 1, lower_bound(tmp2.begin(), tmp2.end(), make_pair((ll)l, 0ll)) - tmp2.begin()); } //#define f(l, r) tr.get_ans(0ll, r, lower_bound(tmp2.begin(), tmp2.end(), make_pair(l, (long long) INF)) - tmp2.begin()) inline bool check(pair<ll, ll> a, pair<ll, ll> b, ll x, ll w, PersSegTree &tr, vector<pair<ll, ll>> &tmp2) { ll lans1 = a.first + f(a.second, x, tr, tmp2) * w; ll lans2 = b.first + f(b.second, x, tr, tmp2) * w; return (lans2 <= lans1); } long long solve(int n, int m, int w, std::vector<int> t, std::vector<int> x, std::vector<int> y, std::vector<int> a, std::vector<int> b, std::vector<int> c, std::vector<int> l, std::vector<int> r) { vector<int> tmp(1, -1); for (auto &i : a) tmp.push_back(i); for (auto &i : b) tmp.push_back(i); for (auto &i : l) tmp.push_back(i); for (auto &i : r) tmp.push_back(i); sort(tmp.begin(), tmp.end()); tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin()); for (auto &i : a) i = lower_bound(tmp.begin(), tmp.end(), i) - tmp.begin(); for (auto &i : b) i = lower_bound(tmp.begin(), tmp.end(), i) - tmp.begin(); for (auto &i : l) i = lower_bound(tmp.begin(), tmp.end(), i) - tmp.begin(); for (auto &i : r) i = lower_bound(tmp.begin(), tmp.end(), i) - tmp.begin(); PersSegTree tr((ll)(tmp.size() + 52)); vector<pair<ll, ll>> tmp2; for (ll i = 0ll; i < w; i++) { tmp2.push_back({l[i], r[i]}); } sort(tmp2.begin(), tmp2.end()); for (ll i = w - 1; i >= 0ll; i--) { tr.update(w - i - 1, tmp2[i].second, 1); } //f(2ll, 2ll); vector<ll> ans_st(m); vector<vector<ll>> all_st(n); for (ll i = 0; i < m; i++) { all_st[x[i]].push_back(a[i]); } all_st[n - 1].push_back(tmp.size() - 1); for (auto &i : all_st) sort(i.begin(), i.end()); vector<vector<pair<ll, pair<ll, ll>>>> ans_end(n); ans_end[0].push_back({0, {0, 0}}); vector<pair<pair<ll, ll>, ll>> que; for (ll i = 0ll; i < m; i++) { que.push_back({{a[i], 0ll}, i}); que.push_back({{b[i], -1ll}, i}); } que.push_back({{tmp.size() - 1, 0}, -1}); sort(que.begin(), que.end()); for (auto &i : que) { if (i.first.second == -1) { ll j = y[i.second]; ll lans = ans_st[i.second] + c[i.second]; if (lans > INF) lans = INF; //ans_end[j].push_back({0, {lans, i.first.first}}); while (ans_end[j].size() > 0 && check(ans_end[j].back().second, {lans, i.first.first}, ans_end[j].back().first, t[j], tr, tmp2)) { ans_end[j].pop_back(); } if (ans_end[j].size() == 0) { ans_end[j].push_back({0, {lans, i.first.first}}); continue; } if (!check(ans_end[j].back().second, {lans, i.first.first}, tmp.size() - 1, t[j], tr, tmp2)) continue; /*ll le = ans_end[j].back().first, ri = tmp.size() - 1; while (ri - le > 1) { ll mid = (le + ri) / 2; if (check(ans_end[j].back().second, {lans, i.first.first}, mid, t[j], tr, tmp2)) { ri = mid; } else { le = mid; } }*/ ll indl = lower_bound(tmp2.begin(), tmp2.end(), make_pair(ans_end[j].back().second.second, 0ll)) - tmp2.begin(); ll indr = lower_bound(tmp2.begin(), tmp2.end(), make_pair(i.first.first, 0ll)) - tmp2.begin(); ll lans52 = tr.get_ans2(indl, indr, ans_end[j].back().second.first, lans, t[j]); //assert(ri == lans52); ans_end[j].push_back({lans52, {lans, i.first.first}}); } else { ll j; if (i.second != -1) { j = x[i.second]; } else { j = n - 1; } ll lans; if (ans_end[j].size() == 0) { lans = INF; } else { auto it = lower_bound(ans_end[j].begin(), ans_end[j].end(), make_pair(i.first.first, make_pair((ll) INF, 0ll))); auto lans2 = (*prev(it)); lans = lans2.second.first + f(lans2.second.second, i.first.first, tr, tmp2) * t[j]; if (lans2.second.first >= INF || lans > INF) lans = INF; //lans = INF; //for (auto &x : ans_end[j]) { // lans = min(lans, x.second.first + f(x.second.second, i.first.first, tr, tmp2) * t[j]); //} } if (i.second == -1) { //cout << lans << endl; if (lans >= INF) { return -1; } else { return lans; } } else { ans_st[i.second] = lans; } } } }

Compilation message (stderr)

train.cpp: In function 'long long int solve(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:195:1: warning: control reaches end of non-void function [-Wreturn-type]
  195 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...