#ifndef LOCAL
#define DEBUG
#endif
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
namespace std {
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
} // namespace std
namespace __gnu_pbds {
template <typename K, typename V=null_type>
using order_statistic_tree = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
}
using __gnu_pbds::order_statistic_tree;
using ll = long long;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int N, M, L, C; cin >> N >> M >> L >> C;
auto Xtrans = [&](int x) -> int {
return L-1-x;
};
vector<int> A(N);
for (int& x : A) {
cin >> x;
x = Xtrans(x);
}
reverse(A.begin(), A.end());
vector<int> B(M);
for (int& x : B) {
cin >> x;
x = Xtrans(x);
}
vector<int> dest(N);
vector<int> dist(N);
for (int i = 0; i < N; i++) {
int tgt = (A[i] + C) % L;
auto it = lower_bound(A.begin(), A.end(), tgt);
if (it == A.end()) {
dest[i] = 0;
dist[i] = C + L + A[0] - tgt;
} else {
dest[i] = int(distance(A.begin(), it));
dist[i] = C + *it - tgt;
}
}
vector<bool> vis(N, false);
vector<bool> isRoot(N, false);
for (int v = 0; v < N; v++) {
if (vis[v]) continue;
int t, h;
for (t = dest[v], h = dest[dest[v]]; !vis[t] && t != h; t = dest[t], h = dest[dest[h]]) {}
if (!vis[t]) {
isRoot[t] = true;
for (int cur = dest[t]; true; cur = dest[cur]) {
vis[cur] = true;
if (cur == t) break;
}
}
for (int cur = v; cur != t; cur = dest[cur]) {
vis[cur] = true;
}
}
vector<vector<int>> evtsAdd(N);
for (int i = 0; i < M; i++) {
auto it = lower_bound(A.begin(), A.end(), B[i]);
if (it == A.end()) {
evtsAdd[0].push_back(L + A[0] - B[i]);
} else {
evtsAdd[distance(A.begin(), it)].push_back(*it - B[i]);
}
}
int Q; cin >> Q;
vector<int> V(Q);
vector<ll> T(Q);
vector<vector<int>> queriesLoc(N);
for (int i = 0; i < Q; i++) {
cin >> V[i] >> T[i];
V[i]--;
V[i] = N-1-V[i];
queriesLoc[V[i]].push_back(i);
}
vector<ll> ans(Q);
vector<vector<int>> ch(N);
for (int v = 0; v < N; v++) {
if (!isRoot[v]) {
ch[dest[v]].push_back(v);
}
}
vector<ll> depth(N);
for (int v = 0; v < N; v++) {
if (!isRoot[v]) continue;
y_combinator([&](auto self, int cur, ll curDepth) -> void {
depth[cur] = curDepth;
for (int nxt : ch[cur]) {
self(nxt, curDepth + dist[nxt]);
}
})(v, 0);
}
mt19937_64 mt(114514);
using tree_t = order_statistic_tree<pair<ll, unsigned long long>>;
vector<tree_t> evtTree(N);
for (int v = 0; v < N; v++) {
if (!isRoot[v]) continue;
int treeInd = y_combinator([&](auto self, int cur) -> int {
int res = cur;
for (auto t : evtsAdd[cur]) {
evtTree[res].insert({t + depth[cur], mt()});
}
for (int nxt : ch[cur]) {
int nres = self(nxt);
if (evtTree[res].size() < evtTree[nres].size()) swap(res, nres);
for (auto t : evtTree[nres]) {
evtTree[res].insert(t);
}
evtTree[nres] = {};
}
for (int it : queriesLoc[cur]) {
ans[it] += evtTree[res].order_of_key({T[it] + depth[cur], -1});
}
return res;
})(v);
ll cycLen = dist[v] + depth[dest[v]];
vector<pair<ll, int>> toProcess;
for (auto t : evtTree[treeInd]) {
toProcess.emplace_back(t.first, -1);
}
for (int cur = dest[v]; true; cur = dest[cur]) {
for (auto it : queriesLoc[cur]) {
toProcess.emplace_back(T[it] - (cycLen - depth[cur]), it);
}
if (cur == v) break;
}
sort(toProcess.begin(), toProcess.end());
tree_t tr;
ll delta = 0;
for (auto it : toProcess) {
ll val = it.first;
int ind = it.second;
if (ind == -1) {
delta -= val / cycLen;
tr.insert({val % cycLen, mt()});
} else {
ans[ind] += delta + ll(tr.size()) * (val / cycLen) + tr.order_of_key({val % cycLen, -1});
}
}
}
for (ll v : ans) {
cout << v << '\n';
}
return 0;
}
Compilation message
harvest.cpp:18:11: error: expected primary-expression before 'auto'
decltype(auto) operator()(Args &&...args) {
^~~~
harvest.cpp:18:11: error: expected ')' before 'auto'
harvest.cpp:18:11: error: expected primary-expression before 'auto'
harvest.cpp:18:11: error: expected primary-expression before 'auto'
harvest.cpp:18:11: error: expected primary-expression before 'auto'
harvest.cpp:18:11: error: expected primary-expression before 'auto'
harvest.cpp:18:2: error: expected unqualified-id before 'decltype'
decltype(auto) operator()(Args &&...args) {
^~~~~~~~
harvest.cpp:24:10: error: expected primary-expression before 'auto'
decltype(auto) y_combinator(Fun &&fun) {
^~~~
harvest.cpp:24:10: error: expected ')' before 'auto'
harvest.cpp:24:10: error: expected primary-expression before 'auto'
harvest.cpp:24:10: error: expected primary-expression before 'auto'
harvest.cpp:24:10: error: expected primary-expression before 'auto'
harvest.cpp:24:10: error: expected primary-expression before 'auto'
harvest.cpp:24:1: error: expected unqualified-id before 'decltype'
decltype(auto) y_combinator(Fun &&fun) {
^~~~~~~~
harvest.cpp: In function 'int main()':
harvest.cpp:123:20: error: use of 'auto' in lambda parameter declaration only available with -std=c++14 or -std=gnu++14
y_combinator([&](auto self, int cur, ll curDepth) -> void {
^~~~
harvest.cpp: In lambda function:
harvest.cpp:126:35: error: 'self' cannot be used as a function
self(nxt, curDepth + dist[nxt]);
^
harvest.cpp: In function 'int main()':
harvest.cpp:123:3: error: 'y_combinator' was not declared in this scope
y_combinator([&](auto self, int cur, ll curDepth) -> void {
^~~~~~~~~~~~
harvest.cpp:136:34: error: use of 'auto' in lambda parameter declaration only available with -std=c++14 or -std=gnu++14
int treeInd = y_combinator([&](auto self, int cur) -> int {
^~~~
harvest.cpp: In lambda function:
harvest.cpp:143:24: error: 'self' cannot be used as a function
int nres = self(nxt);
^
harvest.cpp: In function 'int main()':
harvest.cpp:136:17: error: 'y_combinator' was not declared in this scope
int treeInd = y_combinator([&](auto self, int cur) -> int {
^~~~~~~~~~~~
