#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 = int(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[y]]) vis[y = nxt[y]] = 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 |
12 ms |
14976 KB |
Output is correct |
3 |
Correct |
12 ms |
15204 KB |
Output is correct |
4 |
Correct |
14 ms |
15232 KB |
Output is correct |
5 |
Correct |
12 ms |
15628 KB |
Output is correct |
6 |
Correct |
13 ms |
15596 KB |
Output is correct |
7 |
Correct |
12 ms |
15616 KB |
Output is correct |
8 |
Correct |
11 ms |
15104 KB |
Output is correct |
9 |
Correct |
11 ms |
15104 KB |
Output is correct |
10 |
Correct |
12 ms |
15360 KB |
Output is correct |
11 |
Correct |
11 ms |
15232 KB |
Output is correct |
12 |
Correct |
12 ms |
15360 KB |
Output is correct |
13 |
Correct |
12 ms |
15360 KB |
Output is correct |
14 |
Correct |
13 ms |
15232 KB |
Output is correct |
15 |
Correct |
14 ms |
15360 KB |
Output is correct |
16 |
Correct |
12 ms |
15360 KB |
Output is correct |
17 |
Correct |
12 ms |
15488 KB |
Output is correct |
18 |
Correct |
12 ms |
15360 KB |
Output is correct |
19 |
Correct |
11 ms |
15360 KB |
Output is correct |
20 |
Correct |
12 ms |
15404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
144 ms |
27208 KB |
Output is correct |
2 |
Correct |
248 ms |
38348 KB |
Output is correct |
3 |
Correct |
245 ms |
42352 KB |
Output is correct |
4 |
Correct |
225 ms |
47580 KB |
Output is correct |
5 |
Correct |
286 ms |
67356 KB |
Output is correct |
6 |
Correct |
296 ms |
67288 KB |
Output is correct |
7 |
Correct |
226 ms |
38492 KB |
Output is correct |
8 |
Correct |
253 ms |
47824 KB |
Output is correct |
9 |
Correct |
288 ms |
55252 KB |
Output is correct |
10 |
Correct |
192 ms |
55636 KB |
Output is correct |
11 |
Correct |
387 ms |
55276 KB |
Output is correct |
12 |
Correct |
320 ms |
55376 KB |
Output is correct |
13 |
Correct |
369 ms |
55388 KB |
Output is correct |
14 |
Correct |
289 ms |
55376 KB |
Output is correct |
15 |
Correct |
256 ms |
50984 KB |
Output is correct |
16 |
Correct |
262 ms |
57820 KB |
Output is correct |
17 |
Correct |
250 ms |
57600 KB |
Output is correct |
18 |
Correct |
177 ms |
37976 KB |
Output is correct |
19 |
Correct |
164 ms |
37980 KB |
Output is correct |
20 |
Correct |
197 ms |
45412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
14848 KB |
Output is correct |
2 |
Correct |
12 ms |
14976 KB |
Output is correct |
3 |
Correct |
12 ms |
15204 KB |
Output is correct |
4 |
Correct |
14 ms |
15232 KB |
Output is correct |
5 |
Correct |
12 ms |
15628 KB |
Output is correct |
6 |
Correct |
13 ms |
15596 KB |
Output is correct |
7 |
Correct |
12 ms |
15616 KB |
Output is correct |
8 |
Correct |
11 ms |
15104 KB |
Output is correct |
9 |
Correct |
11 ms |
15104 KB |
Output is correct |
10 |
Correct |
12 ms |
15360 KB |
Output is correct |
11 |
Correct |
11 ms |
15232 KB |
Output is correct |
12 |
Correct |
12 ms |
15360 KB |
Output is correct |
13 |
Correct |
12 ms |
15360 KB |
Output is correct |
14 |
Correct |
13 ms |
15232 KB |
Output is correct |
15 |
Correct |
14 ms |
15360 KB |
Output is correct |
16 |
Correct |
12 ms |
15360 KB |
Output is correct |
17 |
Correct |
12 ms |
15488 KB |
Output is correct |
18 |
Correct |
12 ms |
15360 KB |
Output is correct |
19 |
Correct |
11 ms |
15360 KB |
Output is correct |
20 |
Correct |
12 ms |
15404 KB |
Output is correct |
21 |
Correct |
144 ms |
27208 KB |
Output is correct |
22 |
Correct |
248 ms |
38348 KB |
Output is correct |
23 |
Correct |
245 ms |
42352 KB |
Output is correct |
24 |
Correct |
225 ms |
47580 KB |
Output is correct |
25 |
Correct |
286 ms |
67356 KB |
Output is correct |
26 |
Correct |
296 ms |
67288 KB |
Output is correct |
27 |
Correct |
226 ms |
38492 KB |
Output is correct |
28 |
Correct |
253 ms |
47824 KB |
Output is correct |
29 |
Correct |
288 ms |
55252 KB |
Output is correct |
30 |
Correct |
192 ms |
55636 KB |
Output is correct |
31 |
Correct |
387 ms |
55276 KB |
Output is correct |
32 |
Correct |
320 ms |
55376 KB |
Output is correct |
33 |
Correct |
369 ms |
55388 KB |
Output is correct |
34 |
Correct |
289 ms |
55376 KB |
Output is correct |
35 |
Correct |
256 ms |
50984 KB |
Output is correct |
36 |
Correct |
262 ms |
57820 KB |
Output is correct |
37 |
Correct |
250 ms |
57600 KB |
Output is correct |
38 |
Correct |
177 ms |
37976 KB |
Output is correct |
39 |
Correct |
164 ms |
37980 KB |
Output is correct |
40 |
Correct |
197 ms |
45412 KB |
Output is correct |
41 |
Correct |
372 ms |
57728 KB |
Output is correct |
42 |
Correct |
265 ms |
45164 KB |
Output is correct |
43 |
Correct |
181 ms |
45780 KB |
Output is correct |
44 |
Correct |
246 ms |
55256 KB |
Output is correct |
45 |
Correct |
296 ms |
81144 KB |
Output is correct |
46 |
Correct |
313 ms |
81924 KB |
Output is correct |
47 |
Correct |
320 ms |
83328 KB |
Output is correct |
48 |
Correct |
317 ms |
79960 KB |
Output is correct |
49 |
Correct |
288 ms |
80096 KB |
Output is correct |
50 |
Correct |
245 ms |
49700 KB |
Output is correct |
51 |
Correct |
290 ms |
59064 KB |
Output is correct |
52 |
Correct |
334 ms |
68312 KB |
Output is correct |
53 |
Correct |
332 ms |
67544 KB |
Output is correct |
54 |
Correct |
342 ms |
68444 KB |
Output is correct |
55 |
Correct |
395 ms |
68304 KB |
Output is correct |
56 |
Correct |
396 ms |
71796 KB |
Output is correct |
57 |
Correct |
343 ms |
72564 KB |
Output is correct |
58 |
Correct |
364 ms |
74124 KB |
Output is correct |
59 |
Correct |
318 ms |
70164 KB |
Output is correct |
60 |
Correct |
322 ms |
70608 KB |
Output is correct |
61 |
Correct |
317 ms |
70624 KB |
Output is correct |
62 |
Correct |
348 ms |
60336 KB |
Output is correct |
63 |
Correct |
225 ms |
49504 KB |
Output is correct |
64 |
Correct |
226 ms |
49744 KB |
Output is correct |
65 |
Correct |
239 ms |
50340 KB |
Output is correct |
66 |
Correct |
244 ms |
49872 KB |
Output is correct |
67 |
Correct |
230 ms |
49960 KB |
Output is correct |
68 |
Correct |
219 ms |
49172 KB |
Output is correct |
69 |
Correct |
341 ms |
57548 KB |
Output is correct |
70 |
Correct |
275 ms |
53240 KB |
Output is correct |
71 |
Correct |
319 ms |
57864 KB |
Output is correct |
72 |
Correct |
345 ms |
62608 KB |
Output is correct |