제출 #1096993

#제출 시각아이디문제언어결과실행 시간메모리
1096993RiverFlow은하철도 (APIO24_train)C++17
10 / 100
224 ms82056 KiB
#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); 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) { // cerr << time << nl; 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()) pos.erase(p); while (sz(pos) and *pos.begin() < p) pos.erase(*pos.begin()); } } int query(int time) { if (sz(pos) == 0) return -1; skip(time); return idx[*pos.begin()]; } int key(int x) { return idd[x]; // return lower_bound(all(idx), x) - idx.begin(); } void add(int i, int time) { // ta insert dp[i] vao // va xoa mot so luong pos nhat dinh 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 ; } //xoa bot di thi co can phai tinh lai hay khong-> tao connection //? 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, p)); } } if (*pos.rbegin() > j) { int k = *(--pos.upper_bound(j)); // 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, i)); } } } } ep[N]; namespace SUB { long long sol() { ds.m = w; ds.init(); 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); 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; } dp[i] = 1LL * land[0] * j + e[i].c; } } 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); } } 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); } // 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

컴파일 시 표준 에러 (stderr) 메시지

train.cpp:430:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
  430 | #endif LOCAL
      |        ^~~~~
train.cpp: In function 'long long int SUB::sol()':
train.cpp:289:9: warning: unused variable 'j' [-Wunused-variable]
  289 |     int j = 0;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...