#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<map>
#include<random>
#include<time.h>
#include<cassert>
#include<chrono>
#include<set>
#include<unordered_set>
#include<array>
using namespace std;
#define ull unsigned long long
#define pb push_back
#define ld long double
#define ll long long
#define all(a) a.begin(), a.end()
#define int long long
mt19937_64 rnd(51);
struct SegTree {
vector<ll> t;
SegTree(int n) {
t.resize(4 * n);
}
void update(int v, int l, int r, int pos, ll val) {
if (l == r) {
t[v] += val;
return;
}
int m = (l + r) / 2;
if (pos <= m) {
update(2 * v, l, m, pos, val);
} else {
update(2 * v + 1, m + 1, r, pos, val);
}
t[v] = t[v * 2] + t[v * 2 + 1];
}
ll get(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (tl == l && tr == r) {
return t[v];
}
int tm = (tl + tr) / 2;
return get(2 * v, tl, tm, l, min(r, tm)) + get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}
};
const int N = 2e5 + 10;
vector<int> mas[N];
vector<pair<int, int>> g[N];
bool on_cycle[N];
pair<int, int> go[N];
ll ans[N];
ll dep[N], sz[N];
vector<pair<ll, int>> query[N];
void zhfs(int v) {
sz[v] = mas[v].size();
for (auto [u, c] : g[v]) {
if (!on_cycle[u]) {
dep[u] = dep[v] + c;
sz[v] += sz[u];
zhfs(u);
}
}
}
vector<ll> st[N];
void dfs(int v) {
for (auto i : mas[v]) {
st[v].pb(i + dep[v]);
}
for (auto [u, c] : g[v]) {
if (!on_cycle[u]) {
dfs(u);
if (st[u].size() > st[v].size()) {
swap(st[u], st[v]);
}
}
}
for (auto [u, c] : g[v]) {
if (!on_cycle[u]) {
for (int i : st[u]) {
st[v].pb(i);
}
}
}
if (!on_cycle[v]) {
for (auto [t, i] : query[v]) {
for (auto val : st[v]) {
if (val - dep[v] <= t) {
ans[i]++;
}
}
}
}
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, l, c;
cin >> n >> m >> l >> c;
int left = (c / l) * l;
c %= l;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < m; i++) {
cin >> b[i];
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int v;
ll t;
cin >> v >> t;
v--;
query[v].pb({t, i});
}
int j = 0;
while (j < b.size() && b[j] < a[0]) {
mas[n - 1].pb(b[j] + l - a[n - 1]);
j++;
}
for (int i = 0; i < n; i++) {
while (j < b.size() && (i == n - 1 || a[i + 1] > b[j])) {
mas[i].pb(b[j] - a[i]);
j++;
}
}
assert(j == b.size());
for (int i = 0; i < n; i++) {
a.pb(a[i] + l);
}
j = 0;
for (int i = n; i < 2 * n; i++) {
while (j + 1 < 2 * n && a[i] - a[j + 1] >= c) {
j++;
}
go[i % n] = {j % n, a[i] - a[j] + left};
g[j % n].pb({i % n, a[i] - a[j] + left});
}
vector<bool> used(n);
vector<deque<int>> cycles;
for (int i = 0; i < n; i++) {
if (!used[i]) {
int j = i;
map<int, int> here;
deque<int> arr;
while (!used[j]) {
used[j] = 1;
here[j] = 1;
arr.pb(j);
j = go[j].first;
}
if (here[j]) {
while (arr.front() != j) {
arr.pop_front();
}
cycles.pb(arr);
for (int v : arr) {
on_cycle[v] = 1;
}
}
}
}
for (int i = 0; i < n; i++) {
if (on_cycle[i]) {
zhfs(i);
dfs(i);
}
}
for (auto cycle : cycles) {
int sz = cycle.size();
vector<ll> pr(sz + 1);
for (int i = 0; i < sz; i++) {
int u = cycle[i], v = cycle[(i + 1) % sz];
pr[i + 1] = pr[i] + go[v].second;
}
vector<ll> u, rem;
map<ll, vector<pair<int, int>>> mp;
for (int i = 0; i < sz; i++) {
int v = cycle[i];
for (auto val : st[v]) {
u.pb(val - pr[i]);
rem.pb((val + pr.back() - pr[i]) % pr.back());
}
for (auto [t, ind] : query[v]) {
mp[t - pr[i]].pb({ind, i});
}
}
sort(all(u));
sort(all(rem));
rem.erase(unique(all(rem)), rem.end());
int sz2 = rem.size();
SegTree cnt2(sz2);
int ind = 0;
ll sum = 0;
for (auto [t, arr] : mp) {
while (ind < u.size() && u[ind] <= t) {
sum += (u[ind] + pr.back()) / pr.back();
int k = lower_bound(all(rem), (u[ind] + pr.back()) % pr.back()) - rem.begin();
assert(rem[k] == (u[ind] + pr.back()) % pr.back());
cnt2.update(1, 0, sz2 - 1, k, 1);
ind++;
}
for (auto [pos, i] : arr) {
int real_t = t + pr[i];
int pos2 = upper_bound(all(rem), (real_t % pr.back()) - pr[i]) - rem.begin() - 1;
int pos3 = lower_bound(all(rem), pr.back() - pr[i]) - rem.begin();
for (int j = pos3; j < sz2; j++) {
assert(rem[j] >= pr.back() - pr[i]);
}
ans[pos] += ind * (real_t / pr.back()) - sum;
ans[pos] -= cnt2.get(1, 0, sz2 - 1, pos3, sz2 - 1);
ans[pos] += cnt2.get(1, 0, sz2 - 1, 0, pos2);
int pos4 = upper_bound(all(rem), real_t % pr.back() + pr.back() - pr[i]) - rem.begin() - 1;
if (0 <= pos3 && pos3 <= pos4 && pos4 < sz2) {
ans[pos] += cnt2.get(1, 0, sz2 - 1, pos3, pos4);
}
}
}
for (int i = 0; i < sz; i++) {
int v = cycle[i];
for (auto [t, ind] : query[v]) {
for (int j = 0; j < sz; j++) {
for (auto val : st[cycle[j]]) {
if (val - pr[j] <= t - pr[i]) {
//ans[ind] += t / pr.back() - (val - pr[j] + pr.back()) / pr.back();
if (j <= i) {
ans[ind]++;
}
/*
if (pr.back() - pr[i] <= (val - pr[j] + pr.back()) % pr.back()) {
ans[ind]--;
}
if ((val + pr[i] - pr[j] + pr.back()) % pr.back() <= t % pr.back()) {
ans[ind]++;
}*/
}
}
}
}
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << endl;
}
return 0;
}
Compilation message
harvest.cpp: In function 'void zhfs(long long int)':
harvest.cpp:66:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | for (auto [u, c] : g[v]) {
| ^
harvest.cpp: In function 'void dfs(long long int)':
harvest.cpp:81:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | for (auto [u, c] : g[v]) {
| ^
harvest.cpp:89:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
89 | for (auto [u, c] : g[v]) {
| ^
harvest.cpp:97:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | for (auto [t, i] : query[v]) {
| ^
harvest.cpp: In function 'int main()':
harvest.cpp:134:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | while (j < b.size() && b[j] < a[0]) {
| ~~^~~~~~~~~~
harvest.cpp:139:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | while (j < b.size() && (i == n - 1 || a[i + 1] > b[j])) {
| ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from harvest.cpp:8:
harvest.cpp:144:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | assert(j == b.size());
| ~~^~~~~~~~~~~
harvest.cpp:190:11: warning: unused variable 'u' [-Wunused-variable]
190 | int u = cycle[i], v = cycle[(i + 1) % sz];
| ^
harvest.cpp:201:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
201 | for (auto [t, ind] : query[v]) {
| ^
harvest.cpp:212:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
212 | for (auto [t, arr] : mp) {
| ^
harvest.cpp:213:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
213 | while (ind < u.size() && u[ind] <= t) {
| ~~~~^~~~~~~~~~
harvest.cpp:220:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
220 | for (auto [pos, i] : arr) {
| ^
harvest.cpp:239:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
239 | for (auto [t, ind] : query[v]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
23384 KB |
Output is correct |
| 2 |
Correct |
12 ms |
25528 KB |
Output is correct |
| 3 |
Correct |
24 ms |
25780 KB |
Output is correct |
| 4 |
Correct |
13 ms |
23644 KB |
Output is correct |
| 5 |
Correct |
14 ms |
24148 KB |
Output is correct |
| 6 |
Correct |
14 ms |
24156 KB |
Output is correct |
| 7 |
Correct |
16 ms |
24152 KB |
Output is correct |
| 8 |
Correct |
10 ms |
23644 KB |
Output is correct |
| 9 |
Correct |
10 ms |
23644 KB |
Output is correct |
| 10 |
Correct |
10 ms |
23640 KB |
Output is correct |
| 11 |
Correct |
10 ms |
23644 KB |
Output is correct |
| 12 |
Incorrect |
56 ms |
23900 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
938 ms |
51896 KB |
Output is correct |
| 2 |
Correct |
407 ms |
49020 KB |
Output is correct |
| 3 |
Correct |
497 ms |
184320 KB |
Output is correct |
| 4 |
Correct |
1178 ms |
208528 KB |
Output is correct |
| 5 |
Correct |
550 ms |
85884 KB |
Output is correct |
| 6 |
Correct |
701 ms |
86068 KB |
Output is correct |
| 7 |
Correct |
330 ms |
48264 KB |
Output is correct |
| 8 |
Correct |
343 ms |
48452 KB |
Output is correct |
| 9 |
Execution timed out |
5052 ms |
74556 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
23384 KB |
Output is correct |
| 2 |
Correct |
12 ms |
25528 KB |
Output is correct |
| 3 |
Correct |
24 ms |
25780 KB |
Output is correct |
| 4 |
Correct |
13 ms |
23644 KB |
Output is correct |
| 5 |
Correct |
14 ms |
24148 KB |
Output is correct |
| 6 |
Correct |
14 ms |
24156 KB |
Output is correct |
| 7 |
Correct |
16 ms |
24152 KB |
Output is correct |
| 8 |
Correct |
10 ms |
23644 KB |
Output is correct |
| 9 |
Correct |
10 ms |
23644 KB |
Output is correct |
| 10 |
Correct |
10 ms |
23640 KB |
Output is correct |
| 11 |
Correct |
10 ms |
23644 KB |
Output is correct |
| 12 |
Incorrect |
56 ms |
23900 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
