oj.uz

Submission #217827

# Submission time Handle Problem Language Result Execution time Memory
217827 2020-03-30T22:43:22 Z keko37 Harvest (JOI20_harvest) C++14
100 / 100
 684 ms 164908 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long llint;

const int MAXN = 200005;
const int LOG = 30;

llint n, m, L, C, q, cnt, nodes;
llint man[MAXN * 2], app[MAXN];
llint qind[MAXN], qtime[MAXN], qsol[MAXN];
llint par[MAXN], w[MAXN], is[MAXN], bio[MAXN];
vector <llint> queries[MAXN], ring[MAXN], child[MAXN], dist[MAXN];
tree <llint,  null_type , less_equal<llint> , rb_tree_tag, tree_order_statistics_node_update> st[MAXN], fen;
llint st_ofs[MAXN];
int lef[MAXN * LOG], rig[MAXN * LOG], tour[MAXN * LOG], root[MAXN];

void dfs (int x) {
    bio[x] = 1;
    if (bio[par[x]] == 0) {
        dfs(par[x]);
    } else if (bio[par[x]] == 1) {
        int start = x;
        do {
            ring[cnt].push_back(x);
            is[x] = 1;
            x = par[x];
        } while (x != start);
        cnt++;
    }
    bio[x] = 2;
}

void build_graph () {
    for (int i = 0; i < m; i++) {
        int ind = lower_bound(man, man + 2*n, app[i] + L) - man - 1;
        st[ind % n].insert(app[i] + L - man[ind]);
    }

    llint Cq = C % L;
    for (int i = 0; i < n; i++) {
        int ind = upper_bound(man, man + 2*n, man[i + n] - Cq) - man - 1;
        par[i] = ind % n;
        w[i] = C + man[i + n] - man[ind] - Cq;
    }

    for (int i = 0; i < n; i++) {
        if (bio[i] == 0) dfs(i);
    }
    for (int i = 0; i < n; i++) {
        if (!is[i]) child[par[i]].push_back(i);
    }
}

void subtree (int x) {
    for (auto sus : child[x]) {
        subtree(sus);
        if (st[sus].size() > st[x].size()) {
            st[sus].swap(st[x]);
            swap(st_ofs[sus], st_ofs[x]);
        }
        for (auto val : st[sus]) {
            st[x].insert(val + st_ofs[sus] - st_ofs[x]);
        }
        st[sus].clear();
    }
    if (!is[x]) {
        for (auto u : queries[x]) {
            qsol[u] = st[x].order_of_key(qtime[u] - st_ofs[x] + 1);
        }
        st_ofs[x] += w[x];
    }
}

int build (int len) {
    int curr = ++nodes;
    tour[curr] = 0;
    if (len == 1) return curr;
    lef[curr] = build(len / 2);
    rig[curr] = build(len / 2);
    return curr;
}

int update (int x, int pos, int lo, int hi) {
    int curr = ++nodes;
    if (lo == hi) {
        tour[curr] = tour[x] + 1;
        return curr;
    }
    if (pos <= (lo + hi) / 2) {
        lef[curr] = update(lef[x], pos, lo, (lo + hi) / 2);
        rig[curr] = rig[x];
    } else {
        lef[curr] = lef[x];
        rig[curr] = update(rig[x], pos, (lo + hi) / 2 + 1, hi);
    }
    tour[curr] = tour[lef[curr]] + tour[rig[curr]];
    return curr;
}

int upit (int x, int from, int to, int lo, int hi) {
    if (from <= lo && hi <= to) return tour[x];
    if (hi < from || to < lo) return 0;
    return upit(lef[x], from, to, lo, (lo + hi) / 2) + upit(rig[x], from, to, (lo + hi) / 2 + 1, hi);
}

void solve_comp (int comp) {
    nodes = 0;
    vector <llint> d;
    llint D = 0;

    for (int i = (int)ring[comp].size() - 1; i >= 0; i--) {
        int r = ring[comp][i];
        subtree(r);
        if (i + 1 != ring[comp].size()) D += w[r];
        for (auto len : st[r]) {
            d.push_back(len + st_ofs[r] + D);
            dist[r].push_back(len + st_ofs[r] + D);
        }
    }
    D += w[ring[comp].back()];
    sort(d.begin(), d.end());

    vector <llint> sum(d.size()), ost(d.size());
    for (int i = 0; i < d.size(); i++) {
        sum[i] = d[i] / D;
        if (i > 0) sum[i] += sum[i - 1];
        ost[i] = d[i] % D;
    }

    sort(ost.begin(), ost.end());
    ost.erase(unique(ost.begin(), ost.end()), ost.end());
    int len = 1;
    while (len < ost.size()) len *= 2;
    root[0] = build(len);
    for (int i = 0; i < d.size(); i++) {
        int pos = lower_bound(ost.begin(), ost.end(), d[i] % D) - ost.begin();
        root[i + 1] = update(root[i], pos, 0, len - 1);
    }

    fen.clear();
    llint ofs = 0;
    for (int i = 0; i < ring[comp].size(); i++) {
        int r = (i == 0 ? ring[comp].back() : ring[comp][i - 1]);

        if (i != 0) {
            for (auto path : dist[r]) {
                int pos = lower_bound(d.begin(), d.end(), path) - d.begin();
                fen.insert(pos);
            }
        }

        for (auto u : queries[r]) {
            llint t = qtime[u] - ofs;
            int pos = upper_bound(d.begin(), d.end(), t) - d.begin() - 1;
            if (pos >= 0) {
                qsol[u] += (pos + 1) * (t / D + 1) - sum[pos];
                int ostQ = upper_bound(ost.begin(), ost.end(), t % D) - ost.begin();
                if (ostQ < len) qsol[u] -= upit(root[pos + 1], ostQ, len - 1, 0, len - 1);
            }
            pos = upper_bound(d.begin(), d.end(), t + D) - d.begin() - 1;
            qsol[u] += fen.order_of_key(pos + 1);
        }

        ofs += w[r];
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> L >> C;
    for (int i = 0; i < n; i++) {
        cin >> man[i];
        man[i + n] = man[i] + L;
    }
    for (int i = 0; i < m; i++) {
        cin >> app[i];
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> qind[i] >> qtime[i];
        qind[i]--;
        queries[qind[i]].push_back(i);
    }
    build_graph();
    for (int i = 0; i < cnt; i++) solve_comp(i);
    for (int i = 0; i < q; i++) {
        cout << qsol[i] << '\n';
    }
    return 0;
}

Compilation message

harvest.cpp: In function 'void solve_comp(int)':
harvest.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i + 1 != ring[comp].size()) D += w[r];
             ~~~~~~^~~~~~~~~~~~~~~~~~~~
harvest.cpp:129:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < d.size(); i++) {
                     ~~^~~~~~~~~~
harvest.cpp:138:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (len < ost.size()) len *= 2;
            ~~~~^~~~~~~~~~~~
harvest.cpp:140:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < d.size(); i++) {
                     ~~^~~~~~~~~~
harvest.cpp:147:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ring[comp].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 38264 KB Output is correct
2 Correct 33 ms 38784 KB Output is correct
3 Correct 36 ms 39424 KB Output is correct
4 Correct 38 ms 39548 KB Output is correct
5 Correct 37 ms 39680 KB Output is correct
6 Correct 37 ms 39680 KB Output is correct
7 Correct 38 ms 39792 KB Output is correct
8 Correct 37 ms 39296 KB Output is correct
9 Correct 37 ms 39168 KB Output is correct
10 Correct 37 ms 39380 KB Output is correct
11 Correct 36 ms 39292 KB Output is correct
12 Correct 36 ms 39680 KB Output is correct
13 Correct 37 ms 39672 KB Output is correct
14 Correct 43 ms 39160 KB Output is correct
15 Correct 37 ms 39672 KB Output is correct
16 Correct 38 ms 39680 KB Output is correct
17 Correct 38 ms 39680 KB Output is correct
18 Correct 38 ms 39544 KB Output is correct
19 Correct 37 ms 39544 KB Output is correct
20 Correct 38 ms 39544 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 52708 KB Output is correct
2 Correct 257 ms 70648 KB Output is correct
3 Correct 224 ms 70264 KB Output is correct
4 Correct 231 ms 70500 KB Output is correct
5 Correct 248 ms 93176 KB Output is correct
6 Correct 260 ms 93304 KB Output is correct
7 Correct 221 ms 66152 KB Output is correct
8 Correct 212 ms 66152 KB Output is correct
9 Correct 282 ms 78056 KB Output is correct
10 Correct 205 ms 75252 KB Output is correct
11 Correct 351 ms 76920 KB Output is correct
12 Correct 314 ms 77032 KB Output is correct
13 Correct 347 ms 77160 KB Output is correct
14 Correct 232 ms 74208 KB Output is correct
15 Correct 292 ms 73012 KB Output is correct
16 Correct 241 ms 82296 KB Output is correct
17 Correct 244 ms 82040 KB Output is correct
18 Correct 159 ms 58488 KB Output is correct
19 Correct 163 ms 58608 KB Output is correct
20 Correct 219 ms 72056 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 38264 KB Output is correct
2 Correct 33 ms 38784 KB Output is correct
3 Correct 36 ms 39424 KB Output is correct
4 Correct 38 ms 39548 KB Output is correct
5 Correct 37 ms 39680 KB Output is correct
6 Correct 37 ms 39680 KB Output is correct
7 Correct 38 ms 39792 KB Output is correct
8 Correct 37 ms 39296 KB Output is correct
9 Correct 37 ms 39168 KB Output is correct
10 Correct 37 ms 39380 KB Output is correct
11 Correct 36 ms 39292 KB Output is correct
12 Correct 36 ms 39680 KB Output is correct
13 Correct 37 ms 39672 KB Output is correct
14 Correct 43 ms 39160 KB Output is correct
15 Correct 37 ms 39672 KB Output is correct
16 Correct 38 ms 39680 KB Output is correct
17 Correct 38 ms 39680 KB Output is correct
18 Correct 38 ms 39544 KB Output is correct
19 Correct 37 ms 39544 KB Output is correct
20 Correct 38 ms 39544 KB Output is correct
21 Correct 165 ms 52708 KB Output is correct
22 Correct 257 ms 70648 KB Output is correct
23 Correct 224 ms 70264 KB Output is correct
24 Correct 231 ms 70500 KB Output is correct
25 Correct 248 ms 93176 KB Output is correct
26 Correct 260 ms 93304 KB Output is correct
27 Correct 221 ms 66152 KB Output is correct
28 Correct 212 ms 66152 KB Output is correct
29 Correct 282 ms 78056 KB Output is correct
30 Correct 205 ms 75252 KB Output is correct
31 Correct 351 ms 76920 KB Output is correct
32 Correct 314 ms 77032 KB Output is correct
33 Correct 347 ms 77160 KB Output is correct
34 Correct 232 ms 74208 KB Output is correct
35 Correct 292 ms 73012 KB Output is correct
36 Correct 241 ms 82296 KB Output is correct
37 Correct 244 ms 82040 KB Output is correct
38 Correct 159 ms 58488 KB Output is correct
39 Correct 163 ms 58608 KB Output is correct
40 Correct 219 ms 72056 KB Output is correct
41 Correct 611 ms 153560 KB Output is correct
42 Correct 312 ms 86776 KB Output is correct
43 Correct 185 ms 67304 KB Output is correct
44 Correct 590 ms 141028 KB Output is correct
45 Correct 425 ms 162896 KB Output is correct
46 Correct 436 ms 163792 KB Output is correct
47 Correct 459 ms 164388 KB Output is correct
48 Correct 471 ms 164820 KB Output is correct
49 Correct 464 ms 164908 KB Output is correct
50 Correct 410 ms 138724 KB Output is correct
51 Correct 405 ms 137960 KB Output is correct
52 Correct 654 ms 161384 KB Output is correct
53 Correct 661 ms 160996 KB Output is correct
54 Correct 640 ms 161380 KB Output is correct
55 Correct 558 ms 161380 KB Output is correct
56 Correct 479 ms 158296 KB Output is correct
57 Correct 475 ms 159192 KB Output is correct
58 Correct 482 ms 159932 KB Output is correct
59 Correct 501 ms 159952 KB Output is correct
60 Correct 486 ms 159700 KB Output is correct
61 Correct 490 ms 159832 KB Output is correct
62 Correct 600 ms 124716 KB Output is correct
63 Correct 334 ms 128772 KB Output is correct
64 Correct 345 ms 129076 KB Output is correct
65 Correct 350 ms 128904 KB Output is correct
66 Correct 431 ms 130292 KB Output is correct
67 Correct 418 ms 131176 KB Output is correct
68 Correct 438 ms 129772 KB Output is correct
69 Correct 573 ms 157272 KB Output is correct
70 Correct 540 ms 153572 KB Output is correct
71 Correct 615 ms 154728 KB Output is correct
72 Correct 684 ms 155092 KB Output is correct