Submission #960768

#	Time	Username	Problem	Language	Result	Execution time	Memory
960768		Pring	Harvest (JOI20_harvest)	C++17	5 / 100	247 ms	89376 KiB

harvest

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
 
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
 
// #define int long long
#define int __int128_t
#define ll __int128_t
#define lll __int128_t
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
// using ll = long long;
// using lll = __int128_t;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> PBDS_TREE;
 
const int MXN = 200005;
int n, m, L, adf, a[MXN], b[MXN], q, qid[MXN];
ll qt[MXN];
int p[MXN], pt[MXN];
ll ans[MXN];
vector<pii> edge[MXN];
vector<int> qry[MXN];
bitset<MXN> vis;
PBDS_TREE tr[MXN];
// vector<int> tr[MXN];
ll lz[MXN];
 
istream &operator>>(istream &ss, __int128_t &x) {
    long long y;
    ss >> y;
    x = y;
    return ss;
}
 
ostream &operator<<(ostream &ss, __int128_t x) {
    long long y = x;
    ss << y;
    return ss;
}
 
struct VSET {
    bitset<MXN> b;
    vector<int> v;
    void init() {
        b.reset();
        v.clear();
    }
    void insert(int x) {
        if (b[x]) return;
        b[x] = true;
        v.push_back(x);
    }
    void clear() {
        for (auto &i : v) b[i] = false;
        v.clear();
    }
} sr;
 
struct BIT {
    int n;
    lll val[MXN];
    void init(int _n) {
        n = _n;
        fill(val + 1, val + n + 1, 0);
    }
    void modify(int id, lll v) {
        for (id++; id <= n; id += (id & -id)) val[id] += v;
    }
    lll query(int id) {
        ll ans = 0;
        for (; id > 0; id -= (id & -id)) ans += val[id];
        return ans;
    }
} B;
 
void PUT_TREE() {
    FOR(i, 0, m) {
        int pp = lower_bound(a, a + n, b[i]) - a - 1;
        if (pp == -1) pp += n;
        int x = (b[i] - a[pp] + L) % L;
        debug(i, pp, x);
        tr[pp].insert(x);
        // tr[pp].push_back(x);
    }
}
 
void GET_P() {
    vector<pii> v;
    FOR(i, 0, n) v.push_back(mp(a[i], i));
    FOR(i, 0, n) v.push_back(mp(a[i] + L, i));
    FOR(i, 0, n) {
        auto pp = prev(lower_bound(v.begin(), v.end(), mp(a[i] + L - adf % L, MXN)));
        p[i] = pp -> sc;
        pt[i] = adf / L * L + (a[i] + L - pp -> fs);
        debug(i, p[i], pt[i]);
        edge[p[i]].push_back(mp(pt[i], i));
    }
}
 
void CALC_CYC(vector<ll> &v, vector<pair<ll, int>> &vq, ll C) {
    int n = v.size(), m = vq.size();
    vector<lll> p(1, 0), pc(1, 0);
    FOR(i, 0, n) {
        p.push_back(p.back() + v[i]);
        pc.push_back(pc.back() + (C - v[i] % C) % C);
    }
    B.init(n);
    vector<pair<ll, int>> dist;
    FOR(i, 0, n) dist.push_back(mp((v[i] ? v[i] - 1 : LLONG_MAX), i));
    FOR(i, 0, m) assert(vq[i].fs >= 0);
    FOR(i, 0, m) dist.push_back(mp(vq[i].fs % C, -i - 1));
    sort(dist.begin(), dist.end());
    for (auto &[t, id] : dist) {
        if (id < 0) {
            id = -id - 1;
            auto [Q, aid] = vq[id];
            int s = upper_bound(v.begin(), v.end(), Q) - v.begin();
            if (s == 0) continue;
            lll x = Q * s - p[s] - (pc[s] + t * s + B.query(s));
            assert(x % C == 0);
            // debug(Q, s, aid, x, x / C);
            debug(x, C, x / C);
            ans[aid] += x / C + s;
        } else {
            B.modify(id, -C);
        }
    }
}
 
namespace JELLY {
    void MERGE(int rt, int id, ll w) {
        if (tr[rt].size() >= tr[id].size()) {
            for (auto i : tr[id]) tr[rt].insert(i + lz[id] + w - lz[rt]);
        } else {
            lz[id] += w;
            for (auto i : tr[rt]) tr[id].insert(i + lz[rt] - lz[id]);
            tr[rt].swap(tr[id]);
            swap(lz[rt], lz[id]);
        }
        tr[id].clear();
    }
    void GET_SR() {
        vector<int> ind(n), ban(n);
        queue<int> q;
        FOR(i, 0, n) ind[p[i]]++;
        FOR(i, 0, n) if (ind[i] == 0) q.push(i);
        while (q.size()) {
            int id = q.front();
            q.pop();
            ban[id] = true;
            if (--ind[p[id]] == 0) q.push(p[id]);
        }
        FOR(i, 0, n) {
            if (ban[i]) continue;
            sr.insert(i);
            int now = i;
            while (!ban[now]) {
                ban[now] = true;
                now = p[now];
            }
        }
    }
    void CALC_MERGE(int id, bool f = true) {
        vis[id] = true;
        for (auto &[w, i] : edge[id]) {
            if (vis[i]) continue;
            CALC_MERGE(i);
            MERGE(id, i, w);
        }
        if (f) {
            for (auto &i : qry[id]) {
                ll Q = qt[i] - lz[id];
                // for (auto j : tr[id]) {
                //     if (j <= Q) ans[i]++;
                // }
                int x = tr[id].order_of_key(Q + 1);
                debug(i, x);
                ans[i] += x;
            }
        }
    }
    void SOLVE(int rt) {
        // debug(rt);
        CALC_MERGE(rt, false);
        vector<ll> v;
        for (auto i : tr[rt]) v.push_back(i + lz[rt]);
        vector<pair<ll, int>> vq;
        vector<int> cyc;
        cyc.push_back(rt);
        while (p[cyc.back()] != rt) cyc.push_back(p[cyc.back()]);
        int acc = 0;
        FOR(i, 0, cyc.size()) {
            debug(cyc[i]);
            for (auto &j : qry[cyc[i]]) {
                debug(j);
                // vq.push_back(mp(qt[j] - acc, j));
                if (qt[j] - acc >= 0) vq.push_back(mp(qt[j] - acc, j));
            }
            acc += pt[cyc[i]];
        }
        CALC_CYC(v, vq, acc);
    }
}
 
void miku() {
    cin >> n >> m >> L >> adf;
    FOR(i, 0, n) cin >> a[i];
    FOR(i, 0, m) cin >> b[i];
    cin >> q;
    FOR(i, 0, q) {
        cin >> qid[i] >> qt[i];
        qid[i]--;
        qry[qid[i]].push_back(i);
    }
    PUT_TREE();
    GET_P();
    JELLY::GET_SR();
    for (auto &i : sr.v) {
        debug(i);
        JELLY::SOLVE(i);
    }
    FOR(i, 0, q) {
        assert(ans[i] <= LLONG_MAX);
        cout << (long long) ans[i] << '\n';
    }
}
 
int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}
 

Compilation message (stderr)

harvest.cpp: In function 'void PUT_TREE()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:94:9: note: in expansion of macro 'debug'
   94 |         debug(i, pp, x);
      |         ^~~~~
harvest.cpp: In function 'void GET_P()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:108:9: note: in expansion of macro 'debug'
  108 |         debug(i, p[i], pt[i]);
      |         ^~~~~
harvest.cpp: In function 'void CALC_CYC(std::vector<__int128>&, std::vector<std::pair<__int128, __int128> >&, __int128)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:135:13: note: in expansion of macro 'debug'
  135 |             debug(x, C, x / C);
      |             ^~~~~
harvest.cpp: In function 'void JELLY::CALC_MERGE(__int128, bool)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:190:17: note: in expansion of macro 'debug'
  190 |                 debug(i, x);
      |                 ^~~~~
harvest.cpp: In function 'void JELLY::SOLVE(__int128)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:206:13: note: in expansion of macro 'debug'
  206 |             debug(cyc[i]);
      |             ^~~~~
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:208:17: note: in expansion of macro 'debug'
  208 |                 debug(j);
      |                 ^~~~~
harvest.cpp: In function 'void miku()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:232:9: note: in expansion of macro 'debug'
  232 |         debug(i);
      |         ^~~~~

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