#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;
int n, q;
int nxt[200001], dis[200001];
vector<int> B[200001];
namespace solve1 {
int n, m, l, c;
int A[400001], B[200001];
void solve() {
cin >> n >> m >> l >> c;
for (int i = 1; i <= n; ++i) cin >> A[i], A[i + n] = A[i] + l;
A[0] = A[n] - l;
for (int i = 1; i <= m; ++i) cin >> B[i];
for (int i = n, j = n + n; i > 0; --i) {
while (A[i + n] - A[j] < c % l) --j;
nxt[i] = j > n ? j - n : j;
dis[i] = A[i + n] - A[j];
if (dis[i] < c) dis[i] += (c - dis[i] + l - 1) / l * l;
}
for (int i = 1; i <= m; ++i) {
int j = upper_bound(A, A + (n + 1), B[i]) - A - 1;
::B[j <= 0 ? j + n : j].push_back(B[i] - A[j]);
}
::n = n;
}
}
bool vis[200001];
int cyc[200001];
llong dist[200001];
vector<pll> edge[200001];
vector<pll> qinv[200001];
vector<int> cycle;
llong ans[200001];
namespace fen {
llong fen[200001];
int n;
void init(int N) {
n = N;
for (int i = 1; i <= n; ++i) fen[i] = 0;
}
void update(int i, llong x) {
while (i <= n) {
fen[i] += x;
i += i & -i;
}
}
llong query(int i) {
llong ret = 0;
while (i) {
ret += fen[i];
i -= i & -i;
}
return ret;
}
};
namespace solve_out {
int st[200001], ed[200001], ord;
vector<pll> apples;
vector<pair<pll, int>> queries;
void dfs(int x) {
st[x] = ++ord;
for (int i : B[x]) apples.emplace_back(i + dist[x], x);
for (pll i : qinv[x]) queries.emplace_back(i, x);
for (auto [i, c] : edge[x]) {
dfs(i);
}
ed[x] = ord;
}
void solve() {
for (int cyc_idx : cycle) {
int x = cyc_idx;
do {
for (auto [i, c] : edge[x]) {
if (cyc[i]) continue;
ord = 0;
apples.clear();
queries.clear();
dfs(i);
sort(apples.begin(), apples.end());
sort(queries.begin(), queries.end());
fen::init(ord);
for (int i = 0, j = 0; i < int(queries.size()); ++i) {
auto [p, x] = queries[i];
auto [t, q] = p;
while (j < int(apples.size()) && apples[j].first <= t) {
fen::update(st[apples[j++].second], 1);
}
ans[q] = fen::query(ed[x]) - fen::query(st[x] - 1);
}
}
} while ((x = nxt[x]) != cyc_idx);
}
}
}
namespace solve_in {
struct fenwick2 {
int n;
vector<llong> cp;
vector<int> fen;
void add(llong x) {
cp.push_back(x);
}
void init() {
sort(cp.begin(), cp.end());
cp.erase(unique(cp.begin(), cp.end()), cp.end());
fen.resize((n = cp.size()) + 1, 0);
}
int find(llong x) const {
return upper_bound(cp.begin(), cp.end(), x) - cp.begin();
}
void update(llong i, int x) {
i = find(i);
while (i <= n) {
fen[i] += x;
i += i & -i;
}
}
int query(llong i) const {
i = find(i);
int ret = 0;
while (i) {
ret += fen[i];
i -= i & -i;
}
return ret;
}
};
vector<pll> apples;
void dfs(int x, llong d, int o) {
for (int i : B[x]) {
apples.emplace_back(i + d, o);
}
for (auto [i, c] : edge[x]) {
if (cyc[i]) continue;
dfs(i, d + c, o);
}
}
int rev[200001];
void solve() {
for (int cyc_idx : cycle) {
vector<int> list;
for (int i = nxt[cyc_idx]; i != cyc_idx; i = nxt[i]) list.push_back(i);
list.push_back(cyc_idx);
int n = list.size();
llong len = 0;
for (int i : list) len += dis[i];
apples.clear();
for (int i = 1; i <= n; ++i) {
int x = list[i - 1];
rev[x] = i;
dfs(x, dist[x], i);
}
fenwick2 fen2;
for (auto [a, b] : apples) fen2.add(a % len);
fen2.init();
sort(apples.begin(), apples.end());
vector<pair<pll, int>> queries;
for (int i : list) {
for (pll j : qinv[i]) {
queries.emplace_back(j, rev[i]);
}
}
sort(queries.begin(), queries.end());
llong acnt = 0, asum = 0;
for (int i = 0, j = 0; i < int(queries.size()); ++i) {
auto [p, x] = queries[i];
auto [t, q] = p;
while (j < int(apples.size()) && apples[j].first + len <= t) {
++acnt;
asum += apples[j].first / len + 1;
fen2.update(apples[j++].first % len, 1);
}
ans[q] = acnt * (t / len) - asum;
ans[q] += fen2.query(t % len);
}
fen::init(n);
for (int i = 0, j = 0; i < int(queries.size()); ++i) {
auto [p, x] = queries[i];
auto [t, q] = p;
while (j < int(apples.size()) && apples[j].first <= t) {
fen::update(apples[j++].second, 1);
}
ans[q] += fen::query(x);
}
}
}
}
void dfs(int x, llong d) {
dist[x] = d;
vis[x] = 1;
for (auto [i, c] : edge[x]) {
if (vis[i]) continue;
dfs(i, d + c);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
solve1::solve();
for (int i = 1; i <= n; ++i) {
edge[nxt[i]].emplace_back(i, dis[i]);
}
for (int i = 1; i <= n; ++i) {
if (vis[i]) continue;
int x = i;
while (!vis[nxt[x]]) vis[x = nxt[x]] = 1;
cycle.push_back(x);
int y = i;
while (vis[nxt[x]]) vis[x = nxt[x]] = 0;
y = x;
while (!cyc[nxt[y]]) cyc[y = nxt[y]] = x;
dfs(x, 0);
}
cin >> q;
for (int i = 1; i <= q; ++i) {
llong v, t;
cin >> v >> t;
qinv[v].emplace_back(t + dist[v], i);
}
solve_out::solve();
solve_in::solve();
for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
return 0;
}
Compilation message
harvest.cpp: In function 'void solve_out::dfs(int)':
harvest.cpp:71:24: warning: unused variable 'c' [-Wunused-variable]
for (auto [i, c] : edge[x]) {
^
harvest.cpp: In function 'void solve_out::solve()':
harvest.cpp:80:32: warning: unused variable 'c' [-Wunused-variable]
for (auto [i, c] : edge[x]) {
^
harvest.cpp: In function 'void solve_in::solve()':
harvest.cpp:162:28: warning: unused variable 'b' [-Wunused-variable]
for (auto [a, b] : apples) fen2.add(a % len);
^
harvest.cpp:174:27: warning: unused variable 'x' [-Wunused-variable]
auto [p, x] = queries[i];
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14848 KB |
Output is correct |
| 2 |
Correct |
13 ms |
14976 KB |
Output is correct |
| 3 |
Correct |
12 ms |
15204 KB |
Output is correct |
| 4 |
Execution timed out |
5056 ms |
15104 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
31196 KB |
Output is correct |
| 2 |
Execution timed out |
5060 ms |
43080 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14848 KB |
Output is correct |
| 2 |
Correct |
13 ms |
14976 KB |
Output is correct |
| 3 |
Correct |
12 ms |
15204 KB |
Output is correct |
| 4 |
Execution timed out |
5056 ms |
15104 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
