답안 #1097059

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1097059 2024-10-06T02:31:37 Z RiverFlow 은하철도 (APIO24_train) C++17
10 / 100
1000 ms 82304 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);

        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];

                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 ;
        }

        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));
            int p = idx[k];
            long long t = (dp[i] - dp[p]) / land[ld] + 1;
            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));
            int p = idx[k];
            long long t = (dp[p] - dp[i]) / land[ld] + 1;
            int tim = ds.getK(e[i].b + 1, e[p].b - 1, t);
            if (tim > 0) {
                pq.push(_mp(tim, j));
            }
        }
    }


} 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;
            }
            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;
        }
    }


    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(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);
                }
                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;
                bit.upd(key(meal[id].l), 1);
            }
        }
    }
    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]);
    }
    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:426:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
  426 | #endif LOCAL
      |        ^~~~~
train.cpp: In function 'long long int SUB::sol()':
train.cpp:288:9: warning: unused variable 'j' [-Wunused-variable]
  288 |     int j = 0;
      |         ^
# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 27232 KB Correct.
2 Correct 13 ms 27228 KB Correct.
3 Correct 13 ms 27224 KB Correct.
4 Correct 13 ms 27228 KB Correct.
5 Correct 12 ms 26972 KB Correct.
6 Correct 11 ms 26972 KB Correct.
7 Correct 12 ms 26972 KB Correct.
# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 43588 KB Correct.
2 Correct 130 ms 50200 KB Correct.
3 Correct 13 ms 26968 KB Correct.
4 Correct 20 ms 28760 KB Correct.
5 Correct 11 ms 26972 KB Correct.
6 Correct 105 ms 42436 KB Correct.
7 Correct 11 ms 26972 KB Correct.
8 Correct 95 ms 46768 KB Correct.
9 Correct 136 ms 50116 KB Correct.
# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 43588 KB Correct.
2 Correct 130 ms 50200 KB Correct.
3 Correct 13 ms 26968 KB Correct.
4 Correct 20 ms 28760 KB Correct.
5 Correct 11 ms 26972 KB Correct.
6 Correct 105 ms 42436 KB Correct.
7 Correct 11 ms 26972 KB Correct.
8 Correct 95 ms 46768 KB Correct.
9 Correct 136 ms 50116 KB Correct.
10 Correct 244 ms 75144 KB Correct.
11 Correct 241 ms 82216 KB Correct.
12 Correct 20 ms 28628 KB Correct.
13 Correct 12 ms 26972 KB Correct.
14 Correct 213 ms 73720 KB Correct.
15 Correct 306 ms 82304 KB Correct.
16 Correct 214 ms 74288 KB Correct.
17 Execution timed out 1076 ms 74476 KB Time limit exceeded
18 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 27232 KB Correct.
2 Correct 13 ms 27228 KB Correct.
3 Correct 13 ms 27224 KB Correct.
4 Correct 13 ms 27228 KB Correct.
5 Correct 12 ms 26972 KB Correct.
6 Correct 11 ms 26972 KB Correct.
7 Correct 12 ms 26972 KB Correct.
8 Correct 108 ms 43588 KB Correct.
9 Correct 130 ms 50200 KB Correct.
10 Correct 13 ms 26968 KB Correct.
11 Correct 20 ms 28760 KB Correct.
12 Correct 11 ms 26972 KB Correct.
13 Correct 105 ms 42436 KB Correct.
14 Correct 11 ms 26972 KB Correct.
15 Correct 95 ms 46768 KB Correct.
16 Correct 136 ms 50116 KB Correct.
17 Correct 244 ms 75144 KB Correct.
18 Correct 241 ms 82216 KB Correct.
19 Correct 20 ms 28628 KB Correct.
20 Correct 12 ms 26972 KB Correct.
21 Correct 213 ms 73720 KB Correct.
22 Correct 306 ms 82304 KB Correct.
23 Correct 214 ms 74288 KB Correct.
24 Execution timed out 1076 ms 74476 KB Time limit exceeded
25 Halted 0 ms 0 KB -