Submission #251891

#	Time	Username	Problem	Language	Result	Execution time	Memory
251891		imeimi2000	Harvest (JOI20_harvest)	C++17	100 / 100	396 ms	83328 KiB

harvest

#include <bits/stdc++.h>

using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;

int n, q;
int nxt[200001], dis[200001];
vector<int> B[200001];
namespace solve1 {
    int n, m, l, c;
    int A[400001], B[200001];
    void solve() {
        cin >> n >> m >> l >> c;
        for (int i = 1; i <= n; ++i) cin >> A[i], A[i + n] = A[i] + l;
        A[0] = A[n] - l;
        for (int i = 1; i <= m; ++i) cin >> B[i];
        for (int i = n, j = n + n; i > 0; --i) {
            while (A[i + n] - A[j] < c % l) --j;
            nxt[i] = j > n ? j - n : j;
            dis[i] = A[i + n] - A[j];
            if (dis[i] < c) dis[i] += (c - dis[i] + l - 1) / l * l;
        }
        for (int i = 1; i <= m; ++i) {
            int j = int(upper_bound(A, A + (n + 1), B[i]) - A) - 1;
            ::B[j <= 0 ? j + n : j].push_back(B[i] - A[j]);
        }
        ::n = n;
    }
}

bool vis[200001];
int cyc[200001];
llong dist[200001];
vector<pll> edge[200001];
vector<pll> qinv[200001];
vector<int> cycle;
llong ans[200001];

namespace fen {
    llong fen[200001];
    int n;
    void init(int N) {
        n = N;
        for (int i = 1; i <= n; ++i) fen[i] = 0;
    }
    void update(int i, llong x) {
        while (i <= n) {
            fen[i] += x;
            i += i & -i;
        }
    }
    llong query(int i) {
        llong ret = 0;
        while (i) {
            ret += fen[i];
            i -= i & -i;
        }
        return ret;
    }
};

namespace solve_out {
    int st[200001], ed[200001], ord;
    vector<pll> apples;
    vector<pair<pll, int>> queries;
    void dfs(int x) {
        st[x] = ++ord;
        for (int i : B[x]) apples.emplace_back(i + dist[x], x);
        for (pll i : qinv[x]) queries.emplace_back(i, x);
        for (auto [i, c] : edge[x]) {
            dfs(i);
        }
        ed[x] = ord;
    }
    void solve() {
        for (int cyc_idx : cycle) {
            int x = cyc_idx;
            do {
                for (auto [i, c] : edge[x]) {
                    if (cyc[i]) continue;
                    ord = 0;
                    apples.clear();
                    queries.clear();
                    dfs(i);
                    sort(apples.begin(), apples.end());
                    sort(queries.begin(), queries.end());
                    fen::init(ord);
                    for (int i = 0, j = 0; i < int(queries.size()); ++i) {
                        auto [p, x] = queries[i];
                        auto [t, q] = p;
                        while (j < int(apples.size()) && apples[j].first <= t) {
                            fen::update(st[apples[j++].second], 1);
                        }
                        ans[q] = fen::query(ed[x]) - fen::query(st[x] - 1);
                    }
                }
            } while ((x = nxt[x]) != cyc_idx);
        }
    }
}

namespace solve_in {
    struct fenwick2 {
        int n;
        vector<llong> cp;
        vector<int> fen;
        void add(llong x) {
            cp.push_back(x);
        }
        void init() {
            sort(cp.begin(), cp.end());
            cp.erase(unique(cp.begin(), cp.end()), cp.end());
            fen.resize((n = cp.size()) + 1, 0);
        }
        int find(llong x) const {
            return upper_bound(cp.begin(), cp.end(), x) - cp.begin();
        }
        void update(llong i, int x) {
            i = find(i);
            while (i <= n) {
                fen[i] += x;
                i += i & -i;
            }
        }
        int query(llong i) const {
            i = find(i);
            int ret = 0;
            while (i) {
                ret += fen[i];
                i -= i & -i;
            }
            return ret;
        }
    };
    vector<pll> apples;
    void dfs(int x, llong d, int o) {
        for (int i : B[x]) {
            apples.emplace_back(i + d, o);
        }
        for (auto [i, c] : edge[x]) {
            if (cyc[i]) continue;
            dfs(i, d + c, o);
        }
    }
    int rev[200001];
    void solve() {
        for (int cyc_idx : cycle) {
            vector<int> list;
            for (int i = nxt[cyc_idx]; i != cyc_idx; i = nxt[i]) list.push_back(i);
            list.push_back(cyc_idx);
            int n = list.size();
            llong len = 0;
            for (int i : list) len += dis[i];
            apples.clear();
            for (int i = 1; i <= n; ++i) {
                int x = list[i - 1];
                rev[x] = i;
                dfs(x, dist[x], i);
            }
            fenwick2 fen2;
            for (auto [a, b] : apples) fen2.add(a % len);
            fen2.init();
            sort(apples.begin(), apples.end());
            vector<pair<pll, int>> queries;
            for (int i : list) {
                for (pll j : qinv[i]) {
                    queries.emplace_back(j, rev[i]);
                }
            }
            sort(queries.begin(), queries.end());
            llong acnt = 0, asum = 0;
            for (int i = 0, j = 0; i < int(queries.size()); ++i) {
                auto [p, x] = queries[i];
                auto [t, q] = p;
                while (j < int(apples.size()) && apples[j].first + len <= t) {
                    ++acnt;
                    asum += apples[j].first / len + 1;
                    fen2.update(apples[j++].first % len, 1);
                }
                ans[q] = acnt * (t / len) - asum;
                ans[q] += fen2.query(t % len);
            }
            fen::init(n);
            for (int i = 0, j = 0; i < int(queries.size()); ++i) {
                auto [p, x] = queries[i];
                auto [t, q] = p;
                while (j < int(apples.size()) && apples[j].first <= t) {
                    fen::update(apples[j++].second, 1);
                }
                ans[q] += fen::query(x);
            }
        }
    }
}

void dfs(int x, llong d) {
    dist[x] = d;
    vis[x] = 1;
    for (auto [i, c] : edge[x]) {
        if (vis[i]) continue;
        dfs(i, d + c);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve1::solve();
    for (int i = 1; i <= n; ++i) {
        edge[nxt[i]].emplace_back(i, dis[i]);
    }
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) continue;
        int x = i;
        while (!vis[nxt[x]]) vis[x = nxt[x]] = 1;
        cycle.push_back(x);
        int y = i;
        while (vis[nxt[y]]) vis[y = nxt[y]] = 0;
        y = x;
        while (!cyc[nxt[y]]) cyc[y = nxt[y]] = x;
        dfs(x, 0);
    }
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        llong v, t;
        cin >> v >> t;
        qinv[v].emplace_back(t + dist[v], i);
    }
    solve_out::solve();
    solve_in::solve();
    for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
    return 0;
}

Compilation message (stderr)

harvest.cpp: In function 'void solve_out::dfs(int)':
harvest.cpp:71:24: warning: unused variable 'c' [-Wunused-variable]
         for (auto [i, c] : edge[x]) {
                        ^
harvest.cpp: In function 'void solve_out::solve()':
harvest.cpp:80:32: warning: unused variable 'c' [-Wunused-variable]
                 for (auto [i, c] : edge[x]) {
                                ^
harvest.cpp: In function 'void solve_in::solve()':
harvest.cpp:162:28: warning: unused variable 'b' [-Wunused-variable]
             for (auto [a, b] : apples) fen2.add(a % len);
                            ^
harvest.cpp:174:27: warning: unused variable 'x' [-Wunused-variable]
                 auto [p, x] = queries[i];
                           ^

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75