#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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]);
}
PersSegTree(ll n) {
trs.push_back(build(0ll, n));
}
};
#define f(l, r) tr.get_ans(0ll, r, lower_bound(tmp2.begin(), tmp2.end(), make_pair(l, (long long) 1e9)) - tmp2.begin())
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) * w;
ll lans2 = b.first + f(b.second, x) * 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 (int 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];
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;
}
}
ans_end[j].push_back({ri, {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 = 1e18;
} else {
auto it = lower_bound(ans_end[j].begin(), ans_end[j].end(), make_pair(i.first.first, make_pair((ll) 1e18, 0ll)));
auto lans2 = (*prev(it));
lans = lans2.second.first + f(lans2.second.second, i.first.first) * t[j];
}
if (i.second == -1) {
//cout << lans << endl;
if (lans == 1e18) {
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:159:1: warning: control reaches end of non-void function [-Wreturn-type]
159 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |