oj.uz

Submission #878471

# Submission time Handle Problem Language Result Execution time Memory
878471 2023-11-24T13:10:38 Z vjudge1 Harvest (JOI20_harvest) C++17
100 / 100
 899 ms 232908 KB 
// 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';
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 91216 KB Output is correct
2 Correct 40 ms 92936 KB Output is correct
3 Correct 39 ms 92756 KB Output is correct
4 Correct 42 ms 90824 KB Output is correct
5 Correct 38 ms 90956 KB Output is correct
6 Correct 40 ms 90908 KB Output is correct
7 Correct 44 ms 91216 KB Output is correct
8 Correct 38 ms 90800 KB Output is correct
9 Correct 38 ms 90792 KB Output is correct
10 Correct 39 ms 90808 KB Output is correct
11 Correct 40 ms 90560 KB Output is correct
12 Correct 39 ms 90708 KB Output is correct
13 Correct 41 ms 90776 KB Output is correct
14 Correct 40 ms 92752 KB Output is correct
15 Correct 39 ms 90708 KB Output is correct
16 Correct 41 ms 91140 KB Output is correct
17 Correct 39 ms 90708 KB Output is correct
18 Correct 42 ms 90704 KB Output is correct
19 Correct 40 ms 90648 KB Output is correct
20 Correct 38 ms 90808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 101712 KB Output is correct
2 Correct 302 ms 139060 KB Output is correct
3 Correct 319 ms 143812 KB Output is correct
4 Correct 242 ms 146864 KB Output is correct
5 Correct 331 ms 149328 KB Output is correct
6 Correct 316 ms 149588 KB Output is correct
7 Correct 239 ms 133672 KB Output is correct
8 Correct 265 ms 135140 KB Output is correct
9 Correct 344 ms 148308 KB Output is correct
10 Correct 189 ms 148104 KB Output is correct
11 Correct 402 ms 147120 KB Output is correct
12 Correct 382 ms 147320 KB Output is correct
13 Correct 413 ms 147280 KB Output is correct
14 Correct 225 ms 147040 KB Output is correct
15 Correct 373 ms 143424 KB Output is correct
16 Correct 314 ms 146408 KB Output is correct
17 Correct 269 ms 146180 KB Output is correct
18 Correct 185 ms 112008 KB Output is correct
19 Correct 157 ms 112016 KB Output is correct
20 Correct 202 ms 138884 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 91216 KB Output is correct
2 Correct 40 ms 92936 KB Output is correct
3 Correct 39 ms 92756 KB Output is correct
4 Correct 42 ms 90824 KB Output is correct
5 Correct 38 ms 90956 KB Output is correct
6 Correct 40 ms 90908 KB Output is correct
7 Correct 44 ms 91216 KB Output is correct
8 Correct 38 ms 90800 KB Output is correct
9 Correct 38 ms 90792 KB Output is correct
10 Correct 39 ms 90808 KB Output is correct
11 Correct 40 ms 90560 KB Output is correct
12 Correct 39 ms 90708 KB Output is correct
13 Correct 41 ms 90776 KB Output is correct
14 Correct 40 ms 92752 KB Output is correct
15 Correct 39 ms 90708 KB Output is correct
16 Correct 41 ms 91140 KB Output is correct
17 Correct 39 ms 90708 KB Output is correct
18 Correct 42 ms 90704 KB Output is correct
19 Correct 40 ms 90648 KB Output is correct
20 Correct 38 ms 90808 KB Output is correct
21 Correct 141 ms 101712 KB Output is correct
22 Correct 302 ms 139060 KB Output is correct
23 Correct 319 ms 143812 KB Output is correct
24 Correct 242 ms 146864 KB Output is correct
25 Correct 331 ms 149328 KB Output is correct
26 Correct 316 ms 149588 KB Output is correct
27 Correct 239 ms 133672 KB Output is correct
28 Correct 265 ms 135140 KB Output is correct
29 Correct 344 ms 148308 KB Output is correct
30 Correct 189 ms 148104 KB Output is correct
31 Correct 402 ms 147120 KB Output is correct
32 Correct 382 ms 147320 KB Output is correct
33 Correct 413 ms 147280 KB Output is correct
34 Correct 225 ms 147040 KB Output is correct
35 Correct 373 ms 143424 KB Output is correct
36 Correct 314 ms 146408 KB Output is correct
37 Correct 269 ms 146180 KB Output is correct
38 Correct 185 ms 112008 KB Output is correct
39 Correct 157 ms 112016 KB Output is correct
40 Correct 202 ms 138884 KB Output is correct
41 Correct 672 ms 218916 KB Output is correct
42 Correct 602 ms 231440 KB Output is correct
43 Correct 249 ms 141452 KB Output is correct
44 Correct 398 ms 222960 KB Output is correct
45 Correct 656 ms 230692 KB Output is correct
46 Correct 656 ms 231188 KB Output is correct
47 Correct 689 ms 232728 KB Output is correct
48 Correct 495 ms 231832 KB Output is correct
49 Correct 454 ms 232908 KB Output is correct
50 Correct 482 ms 221472 KB Output is correct
51 Correct 445 ms 221068 KB Output is correct
52 Correct 722 ms 225624 KB Output is correct
53 Correct 685 ms 227572 KB Output is correct
54 Correct 782 ms 225592 KB Output is correct
55 Correct 899 ms 223144 KB Output is correct
56 Correct 673 ms 224792 KB Output is correct
57 Correct 674 ms 225072 KB Output is correct
58 Correct 706 ms 229108 KB Output is correct
59 Correct 492 ms 224996 KB Output is correct
60 Correct 472 ms 225516 KB Output is correct
61 Correct 483 ms 226228 KB Output is correct
62 Correct 712 ms 223848 KB Output is correct
63 Correct 436 ms 184768 KB Output is correct
64 Correct 441 ms 184852 KB Output is correct
65 Correct 439 ms 185496 KB Output is correct
66 Correct 340 ms 184500 KB Output is correct
67 Correct 329 ms 184592 KB Output is correct
68 Correct 332 ms 183848 KB Output is correct
69 Correct 592 ms 223116 KB Output is correct
70 Correct 551 ms 219820 KB Output is correct
71 Correct 610 ms 220200 KB Output is correct
72 Correct 491 ms 220256 KB Output is correct