| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1097057 |
2024-10-06T02:28:20 Z |
RiverFlow |
Train (APIO24_train) |
C++17 |
|
1000 ms |
82316 KB |
#include <bits/stdc++.h>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b or a == -1) { a = b; return 1; } return 0;
}
const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;
struct edge {
int a, b, x, y, c;
edge () {};
edge (int _a, int _b, int _x, int _y, int _c) {
a = _a, b = _b, x = _x, y = _y, c = _c;
}
};
struct meals {
int l, r;
bool operator < (const meals & other) {
return l < other.l;
}
} meal[N];
edge e[N];
int n, m, w, land[N];
vector<int> g[N];
struct data_structure {
struct node {
int l, r, c;
node () {
c = 0;
}
};
vector<node> t;
int ver[N], id[N];
int build(int l, int r) {
int cur = sz(t);
t.push_back(node());
if (l == r) return cur;
int m = (l + r) >> 1;
int a = build(l, m);
int b = build(m + 1, r);
t[cur].l = a, t[cur].r = b;
return cur;
}
int update(int id, int p, int l, int r) {
int cur = sz(t);
t.push_back(node());
t[cur].c = t[id].c + 1;
t[cur].l = t[id].l;
t[cur].r = t[id].r;
if (l == r) return cur;
int m = (l + r) >> 1;
if (p <= m) {
int a = update(t[id].l, p, l, m);
t[cur].l = a;
} else {
int b = update(t[id].r, p, m+1, r);
t[cur].r = b;
}
return cur;
}
int m = 0;
vec<int> val, val2;
void init() {
if (m == 0) return ;
sort(meal, meal + m, [](meals x, meals y) {
return x.l < y.l;
});
val.push_back(0);
FOR(i, 0, m - 1) val.push_back(meal[i].l);
unq(val);
FOR(i, 0, m - 1) val2.push_back(meal[i].r);
unq(val2);
int R = sz(val2);
ver[0] = build(1, R);
// for(int i = 0; i < w; ++i) {
// cerr << meal[i].l << ' ' << meal[i].r << nl;
// }
// cerr << yes << nl;
int c = 0;
FOR(i, 0, m - 1) {
id[i] = lower_bound(all(val2), meal[i].r) - val2.begin() + 1;
}
for(int i = 0, j = i; i < m; i = j + 1) {
while (j + 1 < m and meal[i].l == meal[j + 1].l) ++j;
ver[c + 1] = update(ver[c], id[i], 1, R);
++c;
for(int k = i + 1; k <= j; ++k) {
ver[c] = update(ver[c], id[k], 1, R);
}
}
}
int get(int R, int L, int l, int r, int k) {
if (t[R].c - t[L].c < k) return -1;
if (l == r) return l;
int m = (l + r) >> 1;
int lchild = t[t[R].l].c - t[t[L].l].c;
if (lchild >= k)
return get(t[R].l, t[L].l, l, m, k);
return get(t[R].r, t[L].r, m + 1, r, k - lchild);
}
int getK(int x, int y, long long k) { // -1 -> do not exist
if (x > y or m == 0) return -1;
int lb = lower_bound(all(val), x) - val.begin();
if (lb == sz(val) or val[lb] > y) return -1;
--lb;
int rb = (--upper_bound(all(val), y) - val.begin());
if (t[ver[rb]].c < k) return -1;
int vx = get(ver[rb], ver[lb], 1, sz(val2), (int)k);
if (vx == -1) return -1;
return val2[vx - 1];
}
};
long long dp[N]; //M
template<typename T>
struct fenwick {
int n; vector<T> bit; bool up = 0;
fenwick() {};
fenwick(int _n, bool _up) { n = _n; bit.resize(n + 7); up = _up; }
void upd(int id, T val) {
if (up) for(; id <= n; id += id & -id) bit[id] += val;
else for(; id > 0; id -= id & -id) bit[id] += val;
}
T get(int id) {
T ans = 0;
if (up) for(; id > 0; id -= id & -id) ans += bit[id];
else for(; id <= n; id += id & -id) ans += bit[id];
return ans;
}
};
data_structure ds;
int idd[N];
struct epoint {
int ld = 0;
vector<int> idx;
set<int> pos;
void init(int i) {
ld = i;
sort(all(idx), [&](int x, int y) {
return e[x].b < e[y].b;
});
for(int i = 0; i < sz(idx); ++i) {
idd[idx[i]] = i;
}
}
priority_queue<ii, vec<ii>, greater<ii>> pq; // (value, pair)
void skip(int time) {
while (sz(pq) and pq.top().fi <= time) {
// if it exceeds a value -> then left value is no longer to be true
int p = pq.top().se; pq.pop();
if (pos.find(p) == pos.end()) {
continue ;
}
pos.erase(p);
if (sz(pos) >= 2 and *pos.begin() < p and *pos.rbegin() > p) {
int x = *(--pos.lower_bound(p));
int y = *pos.lower_bound(p);
int i = idx[x], j = idx[y];
// co (i, j)
// dp[i] < dp[j]
long long t = (dp[j] - dp[i]) / land[ld] + 1;
int tim = ds.getK(e[i].b + 1, e[j].b - 1, t);
if (tim > 0) {
pq.push(_mp(tim, x));
}
}
}
}
int query(int time) {
if (sz(pos) == 0) return -1;
skip(time);
return idx[*pos.begin()];
}
int key(int x) {
return idd[x];
}
void add(int i, int time) {
int j = key(i);
if (sz(pos) == 0) {
pos.insert(j);
return ;
}
// cerr << "insert: " << i << ' ' << j << ' ' << time << nl;
// cerr << *pos.rbegin() << ' ' << idx[*pos.rbegin()] << nl;
if (*pos.rbegin() > j and dp[idx[*pos.rbegin()]] <= dp[i]) {
return ;
}
skip(time);
pos.insert(j);
while (sz(pos)) {
if (*pos.begin() == j) break ;
int k = *(--pos.lower_bound(j));
if (dp[idx[k]] >= dp[i]) {
pos.erase(k);
} else
break ;
}
if (*pos.begin() < j) {
int k = *(--pos.lower_bound(j));
// co k
int p = idx[k];
assert(dp[i] >= dp[p]);
long long t = (dp[i] - dp[p]) / land[ld] + 1;
// t thang dau tien / t > 0
int tim = ds.getK(e[p].b + 1, e[i].b - 1, t);
if (tim > 0) {
pq.push(_mp(tim, k));
}
}
if (*pos.rbegin() > j) {
int k = *(--pos.upper_bound(j));
// cerr << yes << nl;
// co k
int p = idx[k];
assert(dp[i] <= dp[p]);
long long t = (dp[p] - dp[i]) / land[ld] + 1;
// t thang dau tien / t > 0
int tim = ds.getK(e[i].b + 1, e[p].b - 1, t);
if (tim > 0) {
pq.push(_mp(tim, j));
}
}
// vec<long long> vl;
// for(auto j : pos) {
// vl.push_back(dp[idx[j]]);
// assert(j < sz(idx));
// }
// assert(is_sorted(all(vl)));
}
} ep[N];
namespace SUB {
long long sol() {
// FOR(i, 0, m - 1) cerr << e[i].x << ' ' << e[i].y << nl;
// FOR(i, 0, w - 1) cerr << meal[i].l << ' ' << meal[i].r << nl;
//
// return -1;
ds.m = w;
ds.init();
// for(int i = 0; i < w; ++i) {
// assert(meal[i].l <= meal[i].r);
// cout << meal[i].l << ' ' << meal[i].r << nl;
// }
sort(meal, meal + w, [](meals x, meals y) {
return x.r < y.r;
});
for(int i = 0; i < m; ++i) {
ep[e[i].y].idx.push_back(i);
}
for(int i = 0; i < n; ++i)
ep[i].init(i);
// ep[2].dbg();
vector<ii> ev;
for(int i = 0; i < m; ++i) {
ev.push_back(_mp(e[i].a, -(i+1)));
ev.push_back(_mp(e[i].b, i+1));
}
const int mx = (int)1e9;
for(int i = 0; i < w; ++i) {
ev.push_back(_mp(meal[i].r, i+mx));
}
int j = 0;
for(int i = 0; i < m; ++i) {
dp[i] = -1;
if (e[i].x == 0) {
int j = 0;
int lb = 0, rb = w - 1;
while (lb <= rb) {
int mid = (lb + rb) >> 1;
if (meal[mid].r < e[i].a) {
j = mid + 1;
lb = mid + 1;
} else
rb = mid - 1;
}
int cnt=0;
FOR(t, 0, w - 1) if (meal[t].r < e[i].a) ++cnt;
assert(cnt == j);
dp[i] = 1LL * land[0] * j + e[i].c;
// ideal[i] = dp[i];
// assert(dp[i] >= ideal[i]);
}
}
vector<int> val;
FOR(i, 0, m - 1) val.push_back(e[i].a - 1), val.push_back(e[i].b + 1);
FOR(i, 0, w - 1) val.push_back(meal[i].l);
unq(val);
auto key = [&](int x) {
return lower_bound(all(val), x) - val.begin() + 1;
};
fenwick<int> bit(sz(val), 1);
sort(ev.begin(), ev.end());
// FOR(i, 0, sz(ev) - 1) cerr << ev[i].fi << ' ' << ev[i].se << nl;
for(int i = 0, j = 0; i < sz(ev); i = j + 1) {
while (j + 1 < sz(ev) and ev[j + 1].fi == ev[i].fi) ++j;
// cerr << "i, j: " << i << ' ' << j << nl;
for(int k = i; k <= j; ++k) {
if (ev[k].se > 0 and ev[k].se < mx) {
int id = ev[k].se - 1;
if (dp[id] == -1) continue ;
int y = e[id].y;
ep[y].add(id, e[id].b);
}
// add vao
}
for(int k = i; k <= j; ++k) {
if (ev[k].se < 0) {
int id = -ev[k].se - 1;
// dp(id)
// cerr<<"id: " << id << nl;
int x = e[id].x;
int p = ep[x].query(e[id].a - 1);
if (p == -1) continue ;
int k = 0;
if (e[id].a >= e[p].b + 2) {
k = bit.get(key(e[id].a - 1)) - bit.get(key(e[p].b + 1) - 1);
}
// int cnt=0;
//// cerr << cnt << ' ' << k << nl;
// FOR(t, 0, w - 1) {
// if (meal[t].r < e[id].a and meal[t].l > e[p].b) {
// ++cnt;
//// cerr << t << nl;
// }
// }
//// cerr << e[p].b + 1 << ' ' << e[id].a - 1 << nl;
// assert(cnt == k);
// cerr << "p: " << p << ' ' << x << ' ' << k << nl;
// cerr << "range: " << e[p].b + 1 << ' ' << e[id].a - 1 << nl;
// cerr << "get: " << key(e[id].a - 1) << ' ' << key(e[p].b + 1) << nl;
// cerr << nl;
mini(dp[id], 1LL * land[x] * k + e[id].c + dp[p]);
}
}
for(int k = i; k <= j; ++k) {
if (ev[k].se >= mx) {
int id = ev[k].se - mx;
// update point -> push l point vao
bit.upd(key(meal[id].l), 1);
// cerr << "update: " << key(meal[id].l) << nl;
}
}
}
sort(meal, meal + w, [](meals x, meals y) {
return x.l < y.l;
});
FOR(i, 0, m - 1) if (dp[i]!=-1){
int lb = 0, rb = w - 1, ans = -1;
while (lb <= rb) {
int m = (lb + rb) >> 1;
if (meal[m].l > e[i].b) {
ans = m;
rb = m - 1;
} else
lb = m + 1;
}
if (ans != -1) {
dp[i] += 1LL * land[e[i].y] * (w-ans);
}
}
long long ans = -1;
FOR(i, 0, m - 1) if (dp[i] != -1 and e[i].y == n - 1) {
mini(ans, dp[i]);
}
// FOR(i, 0, m - 1) cout << dp[i] << ' '; cout << nl;
return ans;
}
};
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 = 0; i < n; ++i) land[i] = T[i];
for(int i = 0; i < m; ++i) {
e[i] = edge(A[i], B[i], X[i], Y[i], C[i]);
g[X[i]].push_back(i);
}
e[m] = edge(0, 0, 0, 0, 0);
for(int i = 0; i < w; ++i) {
meal[i].l = L[i], meal[i].r = R[i];
}
// if (w <= 10 and m <= 1000) {
// return SUB1::sol();
// }
return SUB::sol();
}
#ifdef LOCAL
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
int N, M, W;
assert(3 == scanf("%d %d %d", &N, &M, &W));
std::vector<int> t(N), x(M), y(M), a(M), b(M), c(M), l(W), r(W);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &t[i]));
for (int i = 0; i < M; i++)
assert(5 == scanf("%d %d %d %d %d", &x[i], &y[i], &a[i], &b[i], &c[i]));
for (int i = 0; i < W; i++)
assert(2 == scanf("%d %d", &l[i], &r[i]));
printf("%lld", solve(N, M, W, t, x, y, a, b, c, l, r));
}
#endif LOCAL
Compilation message
train.cpp:482:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
482 | #endif LOCAL
| ^~~~~
train.cpp: In function 'long long int SUB::sol()':
train.cpp:323:9: warning: unused variable 'j' [-Wunused-variable]
323 | int j = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
27224 KB |
Correct. |
| 2 |
Correct |
17 ms |
27084 KB |
Correct. |
| 3 |
Correct |
12 ms |
27228 KB |
Correct. |
| 4 |
Correct |
14 ms |
27228 KB |
Correct. |
| 5 |
Correct |
12 ms |
26972 KB |
Correct. |
| 6 |
Correct |
12 ms |
26972 KB |
Correct. |
| 7 |
Correct |
12 ms |
26972 KB |
Correct. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
43644 KB |
Correct. |
| 2 |
Correct |
154 ms |
50144 KB |
Correct. |
| 3 |
Correct |
13 ms |
26888 KB |
Correct. |
| 4 |
Correct |
22 ms |
28764 KB |
Correct. |
| 5 |
Correct |
13 ms |
26972 KB |
Correct. |
| 6 |
Correct |
112 ms |
42460 KB |
Correct. |
| 7 |
Correct |
11 ms |
27072 KB |
Correct. |
| 8 |
Correct |
104 ms |
46952 KB |
Correct. |
| 9 |
Correct |
146 ms |
50120 KB |
Correct. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
43644 KB |
Correct. |
| 2 |
Correct |
154 ms |
50144 KB |
Correct. |
| 3 |
Correct |
13 ms |
26888 KB |
Correct. |
| 4 |
Correct |
22 ms |
28764 KB |
Correct. |
| 5 |
Correct |
13 ms |
26972 KB |
Correct. |
| 6 |
Correct |
112 ms |
42460 KB |
Correct. |
| 7 |
Correct |
11 ms |
27072 KB |
Correct. |
| 8 |
Correct |
104 ms |
46952 KB |
Correct. |
| 9 |
Correct |
146 ms |
50120 KB |
Correct. |
| 10 |
Correct |
238 ms |
75176 KB |
Correct. |
| 11 |
Correct |
240 ms |
82288 KB |
Correct. |
| 12 |
Correct |
20 ms |
28596 KB |
Correct. |
| 13 |
Correct |
14 ms |
26968 KB |
Correct. |
| 14 |
Correct |
220 ms |
73672 KB |
Correct. |
| 15 |
Correct |
255 ms |
82316 KB |
Correct. |
| 16 |
Correct |
226 ms |
74436 KB |
Correct. |
| 17 |
Execution timed out |
1073 ms |
74680 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
27224 KB |
Correct. |
| 2 |
Correct |
17 ms |
27084 KB |
Correct. |
| 3 |
Correct |
12 ms |
27228 KB |
Correct. |
| 4 |
Correct |
14 ms |
27228 KB |
Correct. |
| 5 |
Correct |
12 ms |
26972 KB |
Correct. |
| 6 |
Correct |
12 ms |
26972 KB |
Correct. |
| 7 |
Correct |
12 ms |
26972 KB |
Correct. |
| 8 |
Correct |
117 ms |
43644 KB |
Correct. |
| 9 |
Correct |
154 ms |
50144 KB |
Correct. |
| 10 |
Correct |
13 ms |
26888 KB |
Correct. |
| 11 |
Correct |
22 ms |
28764 KB |
Correct. |
| 12 |
Correct |
13 ms |
26972 KB |
Correct. |
| 13 |
Correct |
112 ms |
42460 KB |
Correct. |
| 14 |
Correct |
11 ms |
27072 KB |
Correct. |
| 15 |
Correct |
104 ms |
46952 KB |
Correct. |
| 16 |
Correct |
146 ms |
50120 KB |
Correct. |
| 17 |
Correct |
238 ms |
75176 KB |
Correct. |
| 18 |
Correct |
240 ms |
82288 KB |
Correct. |
| 19 |
Correct |
20 ms |
28596 KB |
Correct. |
| 20 |
Correct |
14 ms |
26968 KB |
Correct. |
| 21 |
Correct |
220 ms |
73672 KB |
Correct. |
| 22 |
Correct |
255 ms |
82316 KB |
Correct. |
| 23 |
Correct |
226 ms |
74436 KB |
Correct. |
| 24 |
Execution timed out |
1073 ms |
74680 KB |
Time limit exceeded |
| 25 |
Halted |
0 ms |
0 KB |
- |
