/*
5 3 20 6
0 4 8 12 16
2 11 14
9
4 1932
2 93787
1 89
5 98124798
1 2684
1 137598
3 2
3 8375
4 237
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = int64_t;
using ull = uint64_t;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int ll
int32_t main() {
ios_base::sync_with_stdio(false);
int N, M; ll L, C;
cin >> N >> M >> L >> C;
vector<ll> A(N);
for (int i = 0; i < N; ++i) cin >> A[i], A[i] = L - 1 - A[i]; // for convenience
reverse(A.begin(), A.end());
vector<int> nxt(N);
vector<ll> dist(N);
{
for (int v = 0; v < N; ++v) {
ll newA = (A[v] + C) % L;
int z = lower_bound(A.begin(), A.end(), newA) - A.begin();
if (z == N) {
nxt[v] = 0;
dist[v] = C + L + A[0] - newA;
} else {
nxt[v] = z;
dist[v] = C + A[z] - newA;
}
}
}
vector<vector<ll>> adds(N);
while (M--) {
ll B;
cin >> B;
B = L - 1 - B;
int z = lower_bound(A.begin(), A.end(), B) - A.begin();
if (z == N) {
adds[0].emplace_back(L + A[0] - B);
} else {
adds[z].emplace_back(A[z] - B);
}
}
int Q;
cin >> Q;
vector<vector<pair<ll, int>>> qs(N);
vector<ll> ans(Q);
for (int i = 0; i < Q; ++i) {
int v; ll T;
cin >> v >> T;
--v;
v = N - 1 - v;
qs[v].emplace_back(T, i);
}
vector<bool> isRoot(N);
vector<char> visited(N);
for (int i = 0; i < N; ++i) {
int v = i;
while (!visited[v]) {
visited[v] = 1;
v = nxt[v];
}
if (visited[v] == 1) isRoot[v] = true;
while (visited[v] == 1) {
visited[v] = 2;
v = nxt[v];
}
}
vector<vector<int>> adj(N);
for (int v = 0; v < N; ++v) {
if (!isRoot[v]) {
adj[nxt[v]].emplace_back(v);
}
}
vector<ll> distToRoot(N);
vector<ordered_set<pair<ll, ull>>> vals(N);
for (int i = 0; i < N; ++i) {
if (!isRoot[i]) continue;
function<void(int)> dfs1 = [&](int v) {
for (int u : adj[v]) {
distToRoot[u] = distToRoot[v] + dist[u];
dfs1(u);
}
};
dfs1(i);
function<void(int)> dfs2 = [&](int v) {
for (auto z : adds[v]) {
vals[v].insert({distToRoot[v] + z, rng()});
}
for (int u : adj[v]) {
dfs2(u);
if (int(vals[v].size()) < int(vals[u].size())) {
vals[v].swap(vals[u]);
}
for (auto z : vals[u]) {
vals[v].insert(z);
}
vals[u] = {};
}
for (auto q : qs[v]) {
ans[q.second] += vals[v].order_of_key({q.first + distToRoot[v], -1});
}
};
dfs2(i);
vector<pair<ll, int>> cur_qs;
ll cycleLen = distToRoot[nxt[i]] + dist[i];
int v = i;
while (true) {
for (auto q : qs[v]) {
cur_qs.emplace_back(q.first - (cycleLen - distToRoot[v]), q.second); // must pass through removed edge
}
v = nxt[v];
if (v == i) break;
}
for (auto z : vals[i]) cur_qs.emplace_back(z.first, -1);
sort(cur_qs.begin(), cur_qs.end());
ordered_set<pair<ll, ull>> st;
ll subt = 0;
for (auto q : cur_qs) {
if (q.second == -1) {
st.insert({q.first, rng()});
subt -= (q.first / cycleLen);
} else {
ans[q.second] += (ll(q.first / cycleLen) * ll(st.size()) + st.order_of_key({q.first % cycleLen, -1}) + subt);
}
}
}
for (ll v : ans) cout << v << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
640 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1536 KB |
Output is correct |
| 4 |
Runtime error |
457 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
11400 KB |
Output is correct |
| 2 |
Runtime error |
1075 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
640 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1536 KB |
Output is correct |
| 4 |
Runtime error |
457 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
