oj.uz

Submission #217098

# Submission time Handle Problem Language Result Execution time Memory
217098 2020-03-29T00:59:32 Z keko37 Harvest (JOI20_harvest) C++14
5 / 100
 5000 ms 105848 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 = 40;

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()) {
            swap(st[sus], 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;
    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) {
    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:117:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i + 1 != ring[comp].size()) D += w[r];
             ~~~~~~^~~~~~~~~~~~~~~~~~~~
harvest.cpp:127:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < d.size(); i++) {
                     ~~^~~~~~~~~~
harvest.cpp:136:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (len < ost.size()) len *= 2;
            ~~~~^~~~~~~~~~~~
harvest.cpp:138:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < d.size(); i++) {
                     ~~^~~~~~~~~~
harvest.cpp:145: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 36 ms 38144 KB Output is correct
2 Correct 36 ms 38648 KB Output is correct
3 Correct 43 ms 39288 KB Output is correct
4 Correct 59 ms 39416 KB Output is correct
5 Correct 443 ms 40056 KB Output is correct
6 Correct 447 ms 40312 KB Output is correct
7 Correct 445 ms 40056 KB Output is correct
8 Correct 42 ms 39168 KB Output is correct
9 Correct 39 ms 39168 KB Output is correct
10 Correct 39 ms 39296 KB Output is correct
11 Correct 40 ms 39288 KB Output is correct
12 Correct 38 ms 39544 KB Output is correct
13 Correct 39 ms 39552 KB Output is correct
14 Correct 37 ms 39296 KB Output is correct
15 Correct 248 ms 39672 KB Output is correct
16 Correct 251 ms 39672 KB Output is correct
17 Correct 254 ms 39912 KB Output is correct
18 Correct 252 ms 39800 KB Output is correct
19 Correct 271 ms 39768 KB Output is correct
20 Correct 247 ms 39800 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 48612 KB Output is correct
2 Correct 488 ms 64628 KB Output is correct
3 Correct 227 ms 64252 KB Output is correct
4 Correct 237 ms 63588 KB Output is correct
5 Execution timed out 5085 ms 105848 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 38144 KB Output is correct
2 Correct 36 ms 38648 KB Output is correct
3 Correct 43 ms 39288 KB Output is correct
4 Correct 59 ms 39416 KB Output is correct
5 Correct 443 ms 40056 KB Output is correct
6 Correct 447 ms 40312 KB Output is correct
7 Correct 445 ms 40056 KB Output is correct
8 Correct 42 ms 39168 KB Output is correct
9 Correct 39 ms 39168 KB Output is correct
10 Correct 39 ms 39296 KB Output is correct
11 Correct 40 ms 39288 KB Output is correct
12 Correct 38 ms 39544 KB Output is correct
13 Correct 39 ms 39552 KB Output is correct
14 Correct 37 ms 39296 KB Output is correct
15 Correct 248 ms 39672 KB Output is correct
16 Correct 251 ms 39672 KB Output is correct
17 Correct 254 ms 39912 KB Output is correct
18 Correct 252 ms 39800 KB Output is correct
19 Correct 271 ms 39768 KB Output is correct
20 Correct 247 ms 39800 KB Output is correct
21 Correct 168 ms 48612 KB Output is correct
22 Correct 488 ms 64628 KB Output is correct
23 Correct 227 ms 64252 KB Output is correct
24 Correct 237 ms 63588 KB Output is correct
25 Execution timed out 5085 ms 105848 KB Time limit exceeded
26 Halted 0 ms 0 KB -