Submission #1181495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181495		chaeryeong	Train (APIO24_train)	C++20	0 / 100	155 ms	64832 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
//#include "stub.cpp"
typedef long long ll;
const int MAXN = 4e5 + 25;
const int B = 400;
const int B2 = 300;
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 prop (int l, int r, int node) {
        if (l != r) {
            lazy[tl] += lazy[node];
            lazy[tr] += lazy[node];
        }
        tree[node] += lazy[node];
        lazy[node] = 0;
    }
    void set (int l, int r, int a, ll b, int node) {
        prop(l, r, 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], tree[tr]);
    }
    void update (int l, int r, int a, int b, int c, int node) {
        prop(l, r, node);
        if (l > b || r < a) return;
        if (l >= a && r <= b) {
            lazy[node] += c;
            prop(l, r, node);
            return;
        }
        update(l, mid, a, b, c, tl); update(mid + 1, r, a, b, c, tr);
        tree[node] = min(tree[tl], tree[tr]);
    }
    int get () {
        prop(0, (int)tree.size() - 1, 1);
        return tree[1];
    }
} cur[MAXN / B + 2];
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) {
            cur[i].init((int)ii[i].size());
            heavy.push_back(i);
            if (i == n - 1) {
                for (int j = 0; j < (int)ii[i].size(); j++) {
                    cur[i].set(0, (int)ii[i].size() - 1, j, 0, 1);
                }
            }
        }
    }
    for (int i = 0; i < m; i++) {
       // cout << a[i] << " " << b[i] << " " << " " << x[i] << " " << y[i] << " " << i << '\n';
        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[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] = c[j] + t[n - 1] * 1ll * ds.get((int)cc.size() - 1);
               // cout << j << ": " << dp[j] << " " << " " << ds.get((int)cc.size() - 1) << '\n';
                continue;
            }
            if ((int)ii[y[j]].size() > B) {
                dp[j] = c[j] + cur[y[j]].get();
            } else {
                dp[j] = inf;
                for (auto k : indices[y[j]]) {
                    if (b[j] <= a[k]) {
                        //cout << j << " " << k << " " << dp[k] << " " << c[j] << " " << ds.get(a[k]) << '\n';
                        dp[j] = min(dp[j], c[j] + dp[k] + 1ll * t[y[j]] * ds.get(a[k]));
                    }
                }
            }
           // cout << j << ": " << dp[j] << '\n';
        }
        for (auto j : ee3[i]) {
            ds.add(r[j] + 1);
         //   cout << l[j] << " || " << r[j] << '\n';
            for (auto k : heavy) {
                cur[x[j]].update(0, (int)ii[x[j]].size() - 1, ff(x[j], r[j] + 1), (int)ii[x[j]].size() - 1, t[k], 1);
            }
        }
    }
    ll ret = inf;
    for (int i = 0; i < m; i++) {
        if (x[i] == 0) {
            ret = min(ret, dp[i] + t[0] * 1ll * ds.get(a[i] - 1));
        }
    }
    if (ret == inf) ret = -1;
    return ret;
}   

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