Submission #902976

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
902976	2024-01-11T05:02:42 Z	box	Harvest (JOI20_harvest)	C++17	Compilation error	0 ms	0 KB

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;
pi banned;
bool only_cyc;

void dfs(int i) {
    done[i] = 1;
    for (int j : adj[i]) {
        if (only_cyc && !on_cyc[j]) continue;
        if (!only_cyc && on_cyc[j]) {
            bug(j);
        }
        if (pi(i,j) == banned) continue;
        // bug("EDGE", i, j);
        dfs(j);
        mrg_self(ds[i], ds[j]);
    }
    for (auto x : orig[i]) ds[i].insert(x);
    for (auto x : qry[i]) ans[x] = ds[i].num_leq(T[x]);
    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]);
        orig.at(p).push_back(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+1, P[i]+1, D[i]);
        adj.at(p).push_back(i);
    }
    cin >> Q;
    qry.resize(N);
    ans = T = v64(Q, -i64(1e18));
    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, cerr << "NODE " << x+1 << endl;
        cerr << "DONE" << endl;
        v64 upds;
        int funny = cyc.back();
        bug(funny+1);
        banned = {P.at(funny), funny};
        only_cyc = 0;
        for (int x : cyc) for (auto z : orig[x]) upds.push_back(z+len-pf.at(x));
        for (auto x : cyc) {
            for (int y : adj[x]) if (!on_cyc[y]) {
                dfs(y);
                for (auto [k, v] : ds[y].S) {
                    orig[x].push_back(k+ds[y].tag);
                    upds.push_back(k+ds[y].tag+len-pf.at(x));
                }
            }
        }
        only_cyc = 1;
        dfs(funny);
        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';
}

Compilation message

harvest.cpp: In function 'int main()':
harvest.cpp:8:14: error: expected primary-expression before 'if'
    8 | #define cerr if (0) cerr
      |              ^~
harvest.cpp:126:46: note: in expansion of macro 'cerr'
  126 |         for (auto x : cyc) on_cyc.at(x) = 1, cerr << "NODE " << x+1 << endl;
      |                                              ^~~~