제출 #878471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878471		vjudge1	수확 (JOI20_harvest)	C++17	100 / 100	899 ms	232908 KiB

harvest

// https://oj.uz/problem/view/JOI20_harvest

/*

Main idea based on https://codeforces.com/blog/entry/74871?#comment-593909:

The goal is to create a functional graph with (n + m) vertices.

There are two types of nodes: apple nodes and collector nodes.

There are two types of queries: collector nodes not in a cycle (1)
and collector nodes in a cycle (2).

For the (1) queries, create a segment tree where each node is a
vector containing the heights of every apple node in that range. Each
apple node contributes only log(n) times. Thus, the preparation and
query steps would take n * (log2(n))^2 operations.

For the (2) queries, consider a vertex S as the root of the cycle.
Compute all the first-time T_i that vertex i meets S (if i is in S's
subtree, then it's the second time) for convenience.

For any query (C, T), transform it into queries (1) and (2):

For the (1) part, determine how many vertices can be reached from
C's subtree in that amount of time.

For the (2) part, it becomes (S, T - dist(C, S)).

So basically, all queries are transformed into (S, T).

The length of the cycle is denoted as len.

The answer involves the sum of all (T - T_i) / len + 1 (where T_i <= T).

Sort T so that the (T_i <= T) case is not considered.

The answer is the sum of ((T / len) - (T_i / len) + (T_i % len <= T % len)) for all i.

The modulo part can be easily computed using a fenwick_tree and compression.

Overall : O(n * log2(n) ^ 2)
*/

#include <bits/stdc++.h>
using namespace std;

class segtree_t {
       public:
        segtree_t *left, *right;
        int l, r, m;
        vector<int64_t> val;

        segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val() {
                if (l == r) return;
                left = new segtree_t(l, m);
                right = new segtree_t(m + 1, r);
        }

        void Update(int p, int64_t x) {
                val.emplace_back(x);
                if (l == r) return;
                if (p <= m) {
                        left->Update(p, x);
                } else {
                        right->Update(p, x);
                }
        }

        void Sort() {
                if (l == r) return;
                sort(val.begin(), val.end());
                left->Sort();
                right->Sort();
        }

        int64_t Get(int s, int t, int64_t limit) {
                if (l > t || r < s) return 0;
                if (s <= l && r <= t) {
                        return upper_bound(val.begin(), val.end(), limit) - val.begin();
                }
                return left->Get(s, t, limit) + right->Get(s, t, limit);
        }
};

segtree_t *tree;

template <class T>
class fenwick_t {
       public:
        vector<T> bit;
        int n;

        fenwick_t(int n = 0) : n(n) {
                bit.resize(n + 3, 0);
        }

        void Update(int pos, T val) {
                for (pos++; pos < bit.size(); pos += pos & -pos) {
                        bit[pos] += val;
                }
        }

        T Get(int pos) {
                T res = T(0);
                for (pos++; pos > 0; pos -= pos & -pos) {
                        res += bit[pos];
                }
                return res;
        }

        T Get(int l, int r) {
                return Get(r) - ((l >= 0) ? Get(l - 1) : T(0));
        }
};

const int MAXN = 4e5;

int n, m, l, c;
int a[MAXN], b[MAXN];
int nxt[MAXN];
int64_t dnxt[MAXN];
bool in_cycle[MAXN];
int done[MAXN];
int64_t dcycle[MAXN];
int S[MAXN];
int root[MAXN];
int64_t dS[MAXN];
int64_t cycle_length[MAXN];
int branch[MAXN];
int qa[MAXN];
int64_t qt[MAXN];
int ord[MAXN];
int64_t ans[MAXN];
int cnt[MAXN];
int cur[MAXN];
int64_t sum[MAXN];

int tin[MAXN], tout[MAXN], timer = 0;
int64_t depth[MAXN];

fenwick_t<int> fw[MAXN];
stack<int> st;
vector<int> all_S;
vector<pair<int, int64_t>> adj[MAXN];
vector<int64_t> T[MAXN];
vector<int> which[MAXN];
vector<int64_t> mod[MAXN];

inline int dist(int i, int j) {  // counter-clock-wise
        return i >= j ? i - j : i + l - j;
}

void build_functional_graph() {
        for (int i = 0; i < m; i++) {
                int j = lower_bound(a, a + n, b[i]) - a;
                if (j == 0) j = n;
                j--;
                nxt[i + n] = j;
                dnxt[i + n] = dist(b[i], a[j]);
        }
        for (int i = 0; i < n; i++) {
                int nxt_time = (a[i] - c) % l;
                if (nxt_time < 0) nxt_time += l;
                int j = upper_bound(a, a + n, nxt_time) - a;
                if (j == 0) j = n;
                j--;
                dnxt[i] = c + dist(nxt_time, a[j]);
                nxt[i] = j;
        }
}

void detect_cycles() {
        for (int i = 0; i < n + m; i++) {
                if (done[i]) continue;
                int x = i;
                while (done[x] == 0) {
                        st.emplace(x);
                        done[x] = 1;
                        x = nxt[x];
                }
                if (done[x] == 1) {  // cycle
                        S[x] = x;
                        all_S.emplace_back(x);
                }
                while (st.size()) S[st.top()] = S[x], done[st.top()] = 2, st.pop();
        }

        for (int i : all_S) {
                int x = i;
                int64_t length = 0;
                do {
                        S[x] = i;
                        in_cycle[x] = 1;
                        dcycle[x] = length;
                        length += dnxt[x];
                        x = nxt[x];
                } while (x != i);
                cycle_length[i] = length;
        }
}

void dfs(int u) {
        tin[u] = ++timer;
        for (auto [v, w] : adj[u]) {
                depth[v] = depth[u] + w;
                dfs(v);
        }
        tout[u] = timer;
}  // [tin[u], tout[u]]

void dfs(int u, int id) {
        branch[u] = id;
        for (auto [v, w] : adj[u]) {
                if (in_cycle[v]) continue;
                dS[v] = dS[u] + w;
                dfs(v, id);
        }
}

void prep() {
        for (int i = 0; i < n; i++) {
                if (in_cycle[i] && S[i] == nxt[i]) {
                        nxt[i] = -1;
                        root[S[i]] = i;
                }
        }

        for (int i = 0; i < n + m; i++) {
                if (nxt[i] == -1) continue;
                adj[nxt[i]].emplace_back(i, dnxt[i]);
        }

        set<int> sss;

        for (int i : all_S) {
                assert(sss.find(root[i]) == sss.end());
                sss.emplace(root[i]);
                dfs(root[i]);
        }

        assert(timer == n + m);
        tree = new segtree_t(1, n + m);
        for (int i = 0; i < m; i++) tree->Update(tin[n + i], depth[n + i]);
        tree->Sort();
        for (int i = 0; i < n; i++) {
                if (in_cycle[i]) dfs(i, i);
        }
        for (int i = 0; i < m; i++) T[S[i + n]].emplace_back(dS[i + n] + cycle_length[S[i + n]] - dcycle[branch[i + n]]);
        for (int i : all_S) {
                sort(T[i].begin(), T[i].end());
                int64_t len = cycle_length[i];
                auto &modulo = mod[i];
                for (int64_t j : T[i]) modulo.emplace_back(j % len);
                sort(modulo.begin(), modulo.end());
                modulo.resize(unique(modulo.begin(), modulo.end()) - modulo.begin());
                which[i].resize(T[i].size());
                for (int j = 0; j < which[i].size(); j++) {
                        which[i][j] = lower_bound(modulo.begin(), modulo.end(), T[i][j] % len) - modulo.begin();
                }
                fw[i] = fenwick_t<int>(modulo.size());
        }
}

int64_t solve1(int x, int64_t time_left) {
        int64_t lowest_depth = time_left + depth[x];
        return tree->Get(tin[x], tout[x], lowest_depth);
}

void two_pointer(int i, int64_t time_left) {
        auto &j = cnt[i];
        while (j < which[i].size()) {
                if (T[i][j] > time_left) return;
                sum[i] += T[i][j] / cycle_length[i];
                fw[i].Update(which[i][j], +1);
                j++;
        }
}

int64_t solve2(int x, int64_t time_left) {
        two_pointer(x, time_left);
        int64_t len = cycle_length[x];
        int64_t res = -sum[x] + 1ll * (time_left / len) * cnt[x];
        int limit = upper_bound(mod[x].begin(), mod[x].end(), time_left % len) - mod[x].begin() - 1;
        res += fw[x].Get(limit);
        return res;
}

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        cin >> n >> m >> l >> c;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < m; i++) cin >> b[i];

        build_functional_graph();
        detect_cycles();
        prep();

        int q;
        cin >> q;
        for (int i = 0; i < q; i++) {
                cin >> qa[i] >> qt[i], qa[i]--;
        }

        for (int i = 0; i < q; i++) {
                ans[i] += solve1(qa[i], qt[i]);
        }

        for (int i = 0; i < q; i++) {
                if (!in_cycle[qa[i]]) continue;
                qt[i] -= dcycle[qa[i]];
                qa[i] = S[qa[i]];
        }

        iota(ord, ord + q, 0);
        sort(ord, ord + q, [&](int i, int j) {
                return qt[i] < qt[j];
        });

        for (int z = 0; z < q; z++) {
                int i = ord[z];
                if (!in_cycle[qa[i]]) continue;
                ans[i] += solve2(qa[i], qt[i]);
        }

        for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

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

harvest.cpp: In constructor 'segtree_t::segtree_t(int, int)':
harvest.cpp:54:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val() {
      |                                                 ~~^~~
harvest.cpp: In function 'void prep()':
harvest.cpp:258:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |                 for (int j = 0; j < which[i].size(); j++) {
      |                                 ~~^~~~~~~~~~~~~~~~~
harvest.cpp: In function 'void two_pointer(int, int64_t)':
harvest.cpp:272:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  272 |         while (j < which[i].size()) {
      |                ~~^~~~~~~~~~~~~~~~~
harvest.cpp: In instantiation of 'void fenwick_t<T>::Update(int, T) [with T = int]':
harvest.cpp:275:45:   required from here
harvest.cpp:99:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                 for (pos++; pos < bit.size(); pos += pos & -pos) {
      |                             ~~~~^~~~~~~~~~~~

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