#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;
| ^~~~
