oj.uz

답안 #217095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
217095 2020-03-29T00:47:47 Z keko37 수확 (JOI20_harvest) C++14
5 / 100
 5000 ms 112788 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 = 20;

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

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 38272 KB Output is correct
2 Correct 38 ms 38904 KB Output is correct
3 Correct 42 ms 39296 KB Output is correct
4 Correct 62 ms 39544 KB Output is correct
5 Correct 475 ms 40312 KB Output is correct
6 Correct 458 ms 40256 KB Output is correct
7 Correct 490 ms 40440 KB Output is correct
8 Correct 39 ms 39296 KB Output is correct
9 Correct 47 ms 39296 KB Output is correct
10 Correct 43 ms 39288 KB Output is correct
11 Correct 43 ms 39296 KB Output is correct
12 Correct 39 ms 39544 KB Output is correct
13 Correct 38 ms 39680 KB Output is correct
14 Correct 43 ms 39416 KB Output is correct
15 Correct 255 ms 39800 KB Output is correct
16 Correct 249 ms 39928 KB Output is correct
17 Correct 243 ms 39800 KB Output is correct
18 Correct 250 ms 39804 KB Output is correct
19 Correct 276 ms 39928 KB Output is correct
20 Correct 250 ms 39800 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 48612 KB Output is correct
2 Correct 535 ms 64504 KB Output is correct
3 Correct 250 ms 64248 KB Output is correct
4 Correct 237 ms 70500 KB Output is correct
5 Execution timed out 5111 ms 112788 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 38272 KB Output is correct
2 Correct 38 ms 38904 KB Output is correct
3 Correct 42 ms 39296 KB Output is correct
4 Correct 62 ms 39544 KB Output is correct
5 Correct 475 ms 40312 KB Output is correct
6 Correct 458 ms 40256 KB Output is correct
7 Correct 490 ms 40440 KB Output is correct
8 Correct 39 ms 39296 KB Output is correct
9 Correct 47 ms 39296 KB Output is correct
10 Correct 43 ms 39288 KB Output is correct
11 Correct 43 ms 39296 KB Output is correct
12 Correct 39 ms 39544 KB Output is correct
13 Correct 38 ms 39680 KB Output is correct
14 Correct 43 ms 39416 KB Output is correct
15 Correct 255 ms 39800 KB Output is correct
16 Correct 249 ms 39928 KB Output is correct
17 Correct 243 ms 39800 KB Output is correct
18 Correct 250 ms 39804 KB Output is correct
19 Correct 276 ms 39928 KB Output is correct
20 Correct 250 ms 39800 KB Output is correct
21 Correct 168 ms 48612 KB Output is correct
22 Correct 535 ms 64504 KB Output is correct
23 Correct 250 ms 64248 KB Output is correct
24 Correct 237 ms 70500 KB Output is correct
25 Execution timed out 5111 ms 112788 KB Time limit exceeded
26 Halted 0 ms 0 KB -