oj.uz

Submission #217103

# Submission time Handle Problem Language Result Execution time Memory
217103 2020-03-29T01:12:46 Z keko37 Harvest (JOI20_harvest) C++14
5 / 100
 5000 ms 106036 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()) {
            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;
    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 36 ms 38144 KB Output is correct
2 Correct 35 ms 38656 KB Output is correct
3 Correct 38 ms 39296 KB Output is correct
4 Correct 60 ms 39416 KB Output is correct
5 Correct 435 ms 40184 KB Output is correct
6 Correct 447 ms 40184 KB Output is correct
7 Correct 438 ms 40056 KB Output is correct
8 Correct 39 ms 39296 KB Output is correct
9 Correct 38 ms 39288 KB Output is correct
10 Correct 39 ms 39288 KB Output is correct
11 Correct 38 ms 39288 KB Output is correct
12 Correct 37 ms 39544 KB Output is correct
13 Correct 37 ms 39552 KB Output is correct
14 Correct 39 ms 39288 KB Output is correct
15 Correct 233 ms 39748 KB Output is correct
16 Correct 241 ms 39672 KB Output is correct
17 Correct 247 ms 39672 KB Output is correct
18 Correct 250 ms 39800 KB Output is correct
19 Correct 244 ms 39800 KB Output is correct
20 Correct 251 ms 39820 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 48612 KB Output is correct
2 Correct 482 ms 64740 KB Output is correct
3 Correct 229 ms 63224 KB Output is correct
4 Correct 226 ms 63460 KB Output is correct
5 Execution timed out 5079 ms 106036 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 35 ms 38656 KB Output is correct
3 Correct 38 ms 39296 KB Output is correct
4 Correct 60 ms 39416 KB Output is correct
5 Correct 435 ms 40184 KB Output is correct
6 Correct 447 ms 40184 KB Output is correct
7 Correct 438 ms 40056 KB Output is correct
8 Correct 39 ms 39296 KB Output is correct
9 Correct 38 ms 39288 KB Output is correct
10 Correct 39 ms 39288 KB Output is correct
11 Correct 38 ms 39288 KB Output is correct
12 Correct 37 ms 39544 KB Output is correct
13 Correct 37 ms 39552 KB Output is correct
14 Correct 39 ms 39288 KB Output is correct
15 Correct 233 ms 39748 KB Output is correct
16 Correct 241 ms 39672 KB Output is correct
17 Correct 247 ms 39672 KB Output is correct
18 Correct 250 ms 39800 KB Output is correct
19 Correct 244 ms 39800 KB Output is correct
20 Correct 251 ms 39820 KB Output is correct
21 Correct 163 ms 48612 KB Output is correct
22 Correct 482 ms 64740 KB Output is correct
23 Correct 229 ms 63224 KB Output is correct
24 Correct 226 ms 63460 KB Output is correct
25 Execution timed out 5079 ms 106036 KB Time limit exceeded
26 Halted 0 ms 0 KB -