Submission #1181545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181545		chaeryeong	Train (APIO24_train)	C++20	100 / 100	723 ms	88384 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
//#include "stub.cpp"
typedef long long ll;
const int MAXN = 5e5 + 25;
const int B = 800;
const int B2 = 400;
struct SQRT {
    int f[MAXN], g[MAXN / B2 + 2];
    void add (int x) {
        while (x % B2 != 0) {
            f[x]++;
            x++;
        }
        x /= B2;
        while (x <= MAXN / B2 + 1) {
            g[x]++;
            x++;
        }
    }
    int get (int x) {
        if (x < 0) return 0;
        return f[x] + g[x / B2];
    }
} ds;
vector <int> cc;
int find (int x) {
    return lower_bound(cc.begin(), cc.end(), x) - cc.begin();
}
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
const ll inf = 1e18;
struct SegmentTree {
    vector <ll> tree, lazy;
    void init (int sze) {
        tree.resize(4 * sze);
        lazy.resize(4 * sze);
        for (auto &i : tree) {
            i = inf;
        }
    }
    void set (int l, int r, int a, ll b, int node) {
        if (l == r) {
            tree[node] = min(tree[node], b);
            return;
        }
        if (a <= mid) set(l, mid, a, b, tl);
        else set(mid + 1, r, a, b, tr);
        tree[node] = min(tree[tl] + lazy[tl], tree[tr] + lazy[tr]);
    }
    void update (int l, int r, int a, int b, int c, int node) {
        if (l > b || r < a) return;
        if (l >= a && r <= b) {
            lazy[node] += c;
            return;
        }
        update(l, mid, a, b, c, tl); update(mid + 1, r, a, b, c, tr);
        tree[node] = min(tree[tl] + lazy[tl], tree[tr] + lazy[tr]);
    }
    ll get (int l, int r, int a, int b, int node) {
        if (l > b || r < a) return inf;
        if (l >= a && r <= b) return tree[node] + lazy[node];
        return min(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr)) + lazy[node];
    }
} cur[MAXN / B + 2];
int ind[MAXN];
vector <int> ii[MAXN];
vector <int> heavy;
vector <int> ee1[MAXN], ee2[MAXN], ee3[MAXN];
ll dp[MAXN];
vector <int> indices[MAXN];
int ff (int x, int y) {
    return lower_bound(ii[x].begin(), ii[x].end(), y) - ii[x].begin();
}
ll 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) {
	for (int i = 0; i < w; i++) {
        cc.push_back(l[i]);
        cc.push_back(r[i]);
    }
    for (int i = 0; i < m; i++) {
        cc.push_back(a[i]);
        cc.push_back(b[i]);
    }
    sort(cc.begin(), cc.end());
    cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
    for (int i = 0; i < w; i++) {
        l[i] = find(l[i]);
        r[i] = find(r[i]);
    }
    for (int i = 0; i < m; i++) {
        a[i] = find(a[i]);
        b[i] = find(b[i]);
        ii[x[i]].push_back(a[i]);
        indices[x[i]].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        ii[i].push_back((int)cc.size() + 2);
        sort(ii[i].begin(), ii[i].end());
        ii[i].resize(unique(ii[i].begin(), ii[i].end()) - ii[i].begin());
        if ((int)ii[i].size() > B) {
            ind[i] = heavy.size();
            heavy.push_back(i);
            cur[ind[i]].init((int)ii[i].size());
            if (i == n - 1) {
                for (int j = 0; j < (int)ii[i].size(); j++) {
                    cur[ind[i]].set(0, (int)ii[i].size() - 1, j, 0, 1);
                }
            }
        }
    }
    for (int i = 0; i < m; i++) {
        ee1[b[i]].push_back(i);
        ee2[a[i]].push_back(i);
    }
    for (int i = 0; i < w; i++) {
        ee3[l[i]].push_back(i);
    }
    for (int i = (int)cc.size() - 1; i >= 0; i--) {
        for (auto j : ee2[i]) {
            if ((int)ii[x[j]].size() > B) {
                cur[ind[x[j]]].set(0, (int)ii[x[j]].size() - 1, ff(x[j], i), dp[j], 1);
            }
        }
        for (auto j : ee1[i]) {
            if (y[j] == n - 1) {
                dp[j] = (ll)c[j] + (ll)t[n - 1] * (ll)ds.get(MAXN - 1);
                continue;
            }
            if ((int)ii[y[j]].size() > B) {
                dp[j] = c[j] + cur[ind[y[j]]].get(0, (int)ii[y[j]].size() - 1, ff(y[j], b[j]), (int)ii[y[j]].size() - 1, 1);;
            } else {
                dp[j] = inf;
                for (auto k : indices[y[j]]) {
                    if (b[j] <= a[k]) {
                        dp[j] = min(dp[j], c[j] + dp[k] + (ll)t[y[j]] * (ll)ds.get(a[k]));
                    }
                }
            }
        }
        for (auto j : ee3[i]) {
            ds.add(r[j] + 1);
            for (auto k : heavy) {
                cur[ind[k]].update(0, (int)ii[k].size() - 1, ff(k, r[j] + 1), (int)ii[k].size() - 1, t[k], 1);
            }
        }
    }
    ll ret = inf;
    for (int i = 0; i < m; i++) {
        if (x[i] == 0) {
            ret = min(ret, dp[i] + (ll)t[0] * (ll)ds.get(a[i]));
        }
    }
    if (ret == inf) ret = -1;
    return ret;
}   

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60