제출 #217827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
217827		keko37	수확 (JOI20_harvest)	C++14	100 / 100	684 ms	164908 KiB

harvest

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75