| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1184808 | anmattroi | Train (APIO24_train) | C++17 | 0 ms | 0 KiB |
#include "train.h"
#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
using il = pair<int, int64_t>;
using li = pair<int64_t, int>;
int n, m, w, t[maxn];
ii deleted[maxn], notDeleted[maxn];
int notDeletedSz = 0, deletedSz = 0;
int prefixSumLeft[maxn], prefixSumRight[maxn];
int leftEnds[maxn], rightEnds[maxn];
struct edge {int x, y, a, b, c;} edges[maxn];
ii meals[maxn];
int e[maxn];
int64_t nho[maxn];
int64_t kc[maxn];
int start[maxn], stop[maxn];
void edgePickerSolve() {
sort(meals + 1, meals + w + 1, [&](const ii &x, const ii &y) {
if (x.fi != y.fi) return x.fi < y.fi;
return x.se > y.se;
});
if (1) {
int rightEnd = INT_MIN;
for (int i = 1; i <= w; i++) {
if (meals[i].se <= rightEnd) deleted[++deletedSz] = meals[i];
else {
notDeleted[++notDeletedSz] = meals[i];
rightEnd = meals[i].se;
}
}
}
for (int i = 1; i <= notDeletedSz; i++) {
leftEnds[i] = notDeleted[i].fi;
rightEnds[i]= notDeleted[i].se;
++prefixSumLeft[i];
++prefixSumRight[i];
}
for (int i = 1, j = 1; i <= deletedSz; i++) {
while (j <= notDeletedSz && leftEnds[j] <= deleted[i].fi) ++j;
++prefixSumLeft[--j];
}
for (int i = 1, j = 1; i <= deletedSz; i++) {
while (j <= notDeletedSz && rightEnds[j] < deleted[i].se) ++j;
++prefixSumRight[j];
}
for (int i = 1; i <= notDeletedSz; i++) {
prefixSumLeft[i] += prefixSumLeft[i-1];
prefixSumRight[i] += prefixSumRight[i-1];
}
}
int64_t st[4*maxn];
void upd(int u, int64_t d, int r = 1, int lo = 1, int hi = m) {
if (lo == hi) {
st[r] = d;
return;
}
int mid = (lo + hi) >> 1;
if (u <= mid) upd(u, d, r<<1, lo, mid);
else upd(u, d, r<<1|1, mid+1, hi);
st[r] = min(st[r<<1], st[r<<1|1]);
}
int64_t get(int u, int v, int r = 1, int lo = 1, int hi = m) {
if (u <= lo && hi <= v) return st[r];
int mid = (lo + hi) >> 1;
return min(u <= mid ? get(u, v, r<<1, lo, mid) : LLONG_MAX/2,
v > mid ? get(u, v, r<<1|1, mid+1, hi) : LLONG_MAX/2);
}
int64_t mainProgram() {
edgePickerSolve();
sort(edges + 1, edges + m + 1, [&](const edge &u, const edge &v) {
if (u.y != v.y) return u.y < v.y;
if (u.b != v.b) return u.b < v.b;
return u.x < v.x;
});
for (int i = 1; i <= m; i++) {
auto [x, y, a, b, c] = edges[i];
if (!start[y]) start[y] = i;
stop[y] = i;
nho[i] = c;
nho[i] += 1LL * prefixSumRight[lower_bound(rightEnds + 1, rightEnds + notDeletedSz + 1, a) - rightEnds - 1] * t[x];
nho[i] -= 1LL * prefixSumLeft [upper_bound(leftEnds + 1, leftEnds + notDeletedSz + 1, b) - leftEnds - 1] * t[y];
}
for (int i = 1; i <= 4*m; i++) st[i] = LLONG_MAX/2;
iota(e + 1, e + m + 1, 1);
sort(e + 1, e + m + 1, [&](int x, int y) {
if (edges[x].b != edges[y].b) return edges[x].b < edges[y].b;
return edges[x].a < edges[y].a;
});
for (int o = 1; o <= m; o++) {
int i = e[o];
auto [x, y, a, b, c] = edges[i];
int ST = start[x], EN = stop[x];
kc[i] = LLONG_MAX/2;
if (ST!=0) {
int L = ST, R;
if (1) {
int lo = ST-1, hi = EN+1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (edges[mid].b <= a) lo = mid;
else hi = mid;
}
R = lo;
}
if (L <= R) kc[i] = min(LLONG_MAX/2, get(L, R) + nho[i]);
}
if (edges[i].x == 1)
kc[i] = min(kc[i], nho[i]);
upd(i, kc[i]);
}
int64_t ans = LLONG_MAX/2;
for (int i = 1; i <= m; i++)
if (kc[i] != LLONG_MAX/2 && edges[i].y == n)
ans = min(ans, kc[i]);
return ans + 1LL * t[n] * w;
}
long long solve(int N, int M, int W, vector<int> T,
vector<int> X, vector<int> Y, vector<int> A, vector<int> B, vector<int> C,
vector<int> L, vector<int> R) {
n = N; m = M; w = W;
for (int i = 1; i <= n; i++) t[i] = T[i-1];
for (int i = 1; i <= m; i++) edges[i] = edge{X[i-1]+1, Y[i-1]+1, A[i-1], B[i-1], C[i-1]};
for (int i = 1; i <= w; i++) meals[i] = ii{L[i-1], R[i-1]};
return mainProgram();
}
/*
3 3 1
20 30 40
0 1 1 15 10
1 2 20 30 5
0 2 18 40 40
16 19
40
*/