Submission #902894

#	Time	Username	Problem	Language	Result	Execution time	Memory
902894		box	수확 (JOI20_harvest)	C++17	0 / 100	5027 ms	486404 KiB

harvest

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (0) cerr
#define bug(...)
#endif

#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef vector<i64> v64;
typedef pair<int, int> pi;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template <class K> using oset = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

struct DS {
    oset<pair<i64, int>> S; i64 tag = 0;
    constexpr int size() { return sz(S); }
    void insert(i64 v) { S.insert({v - tag, sz(S)}); }
    void extend(i64 v) { tag += v; }
    int num_leq(i64 v) { return S.order_of_key({v - tag, INT_MAX}); }
    void pr() {
        for (auto [k,v] : S) cout << k+tag << ' ';
        cout << '\n';
    }
};
void mrg_self(DS &me, DS &ds) {
    if (me.size() < ds.size()) swap(me, ds);
    for (auto [k, v] : exchange(ds.S, {})) me.insert(k+ds.tag);
}

i64 fdiv(i64 a, i64 b) {
    return a/b - ((a^b) < 0 && a%b);
}

int N, M, L, C, Q;
vi A, B, P;
vector<vi> adj;
vector<DS> ds;
v64 D, pf;
vector<v64> orig;
vi done, on_cyc;
vector<vi> qry;
v64 T, ans;
vi nodes;
pi banned;
bool ban_cyc;

void dfs(int i, bool top) {
    nodes.push_back(i);
    done[i] = 1;
    for (int j : adj[i]) {
        if (!ban_cyc && pi(i,j) == banned) continue;
        if (ban_cyc && on_cyc[j]) continue;
        // bug("EDGE", i, j);
        dfs(j, 0);
        ds[j].extend(D[j]);
        mrg_self(ds[i], ds[j]);
    }
    // cout << "\t\t\t" << i << ": "; 
    // ds[i].pr();
    if (top) return;
    for (auto x : qry[i]) {
        ans[x] += ds[i].num_leq(T[x]);
        // bug(x, T[x], ans[x]);
        ds[i].pr();
    }
    // ds[i].extend(D[i]);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> L >> C;
    A = vi(N), B = vi(M);
    for (auto &x : A) cin >> x;
    for (auto &x : B) cin >> x;
    orig.resize(N);
    ds.resize(N);
    for (auto x : B) {
        int y = x;
        if (y < A[0]) y += L;
        int p = upper_bound(all(A), y)-begin(A)-1;
        // bug(p, y-A[p]);
        ds.at(p).insert(y-A[p]);
    }
    P = vi(N), D = v64(N);
    adj.resize(N);
    for (int i = 0; i < N; i++) {
        int y = (A[i]-C)%L;
        if (y < 0) y += L;
        if (y < A[0]) y += L;
        int p = upper_bound(all(A), y)-begin(A)-1;
        assert(0 <= p && p < N);
        P[i] = p;
        D[i] = C + (y-A[p]);
        // bug(i, P[i], D[i]);
        adj.at(p).push_back(i);
    }
    cin >> Q;
    qry.resize(N);
    ans = T = v64(Q);
    for (int i = 0; i < Q; i++) {
        int v; cin >> v >> T[i], v--;
        qry.at(v).push_back(i);
    }
    done = on_cyc = vi(N);
    pf.resize(N);
    for (int i = 0; i < N; i++) {
        if (done[i]) continue;
        int x = i, y = P.at(i);
        while (x != y) x = P.at(x), y = P.at(P.at(y));
        vi cyc;
        do {
            done[x] = 1;
            cyc.push_back(x);
            x = P[x];
        } while (!done[x]);
        i64 len = 0;
        for (int x : cyc) {
            pf[x] = len;
            len += D[x];
        }
        for (auto x : cyc) on_cyc.at(x) = 1;
        v64 upds;
        int funny = cyc.back();
        banned = {P.at(funny), funny};
        ban_cyc = 1;
        for (auto x : cyc) {
            if (x == funny) ban_cyc = 0;
            dfs(x, x != funny);
            if (x != funny) for (auto [k, v] : ds[x].S) upds.push_back(k+ds[x].tag+len-pf.at(x));
        }
        vector<pair<i64, int>> qrys;
        for (int x : cyc) for (int y : qry[x]) qrys.push_back({T[y]-pf.at(x), y});
        sort(all(qrys));
        sort(all(upds), greater<>());
        DS ds; i64 con = 0;
        for (auto [v, y] : qrys) {
            while (sz(upds) && upds.back() <= v) {
                // bug(upds.back());
                ds.insert(upds.back()%len);
                con += fdiv(upds.back(), len);
                upds.pop_back();
            }
            // bug(y, v);
            ans.at(y) += fdiv(v,len)*ds.size()-con+ds.num_leq(v%len);
        }

    }
    for (auto x : ans) cout << x << '\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 75