/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 5e5+100, M = 1e5+10, K = 52, MX = 30;
typedef tree<pair<ll, int>, null_type, less<pair<ll, int>>, rb_tree_tag, tree_order_statistics_node_update> oset;
int n, m, q, loop_id[N], cnt = 0;
ll L, C, a[N], b[N], cycle_size[N];
vector<pair<ll, int>> Q[N];
ll ANS[N];
array<ll, 2> go[N];
vector<pair<int, ll>> g[N];
vector<ll> G[N];
oset T[N];
vector<bool> vis;
int st;
void dfs(int v, ll dep){
vis[v] = 1;
// cerr << v << " dfs\n";
int big = -1;
for(auto [u, w]: g[v]){
if(u == st) continue;
dfs(u, dep + w);
if(big == -1 || T[u].size() > T[big].size()) big = u;
}
if(big != -1){
T[v].swap(T[big]);
}
for(ll x: G[v]) T[v].insert({x + dep, cnt++});
for(auto [u, w]: g[v]){
if(u != big && u != st){
for(auto x: T[u]) T[v].insert(x);
T[u].clear();
}
}
for(auto [t, idx]: Q[v]){
int num = T[v].order_of_key(pair<ll, int>{t + dep + 1, -1});
ANS[idx] = num;
}
}
void solve(){
cin >> n >> m >> L >> C;
for(int i = 1; i <= n; ++i){
cin >> a[i];
loop_id[i] = 0;
}
for(int i = n+1; i <= 2*n; ++i) a[i] = a[i-n] + L;
for(int i = 1; i <= m; ++i){
cin >> b[i];
}
cin >> q;
for(int i = 1; i <= q; ++i){
int p; cin >> p;
ll t; cin >> t;
Q[p].pb({t, i});
ANS[i] = 0;
}
ll num = C/L, c = C%L;
for(int i = 1; i <= n; ++i){
int l = i+1, r = i+n, res = i+n;
while(l <= r){
int mid = l+r>>1;
if(a[i + n] - a[mid] >= c){
res = mid;
l = mid+1;
}else{
r = mid-1;
}
}
go[i] = {res > n ? res-n : res, num * L + a[i+n] - a[res]};
}
int id = 0;
vis.resize(n + 1);
for(int i = 1; i <= n; ++i){
if(!vis[i]){
int v = i;
stack<int> st;
while(!vis[v]){
st.push(v);
// cerr << v << '\n';
vis[v] = 1;
v = go[v][0];
}
vi loop;
loop.pb(v);
while(st.size() && st.top() != v){
loop.pb(st.top());
st.pop();
}
if(st.empty() || st.top() != v){
continue;
}
id++;
cycle_size[id] = 0;
for(int x: loop){
loop_id[x] = id;
cycle_size[id] += go[x][1];
}
}
}
for(int i = 1; i <= n; ++i){
g[go[i][0]].pb({i, go[i][1]});
}
for(int i = 1; i <= m; ++i){
int res = upper_bound(a+1, a+1+n, b[i]) - a;
--res;
ll d;
if(res == 0){
res = n;
d = b[i] - a[res] + L;
}else{
d = b[i] - a[res];
}
if(res == n + 1) res = 1;
G[res].pb(d);
// cerr << res << ' ' << d << '\n';
}
// en;
// for(int i = 1; i <= n; ++i){
// cerr << go[i][0] << ' ' << go[i][1] << '\n';
// }
// en;
vis.clear();
vis.resize(n + 1);
for(int i = 1; i <= n; ++i){
if(loop_id[i] && !vis[i]){
st = i;
dfs(i, 0ll);
// we managed to carry all apples to the vertex i, now we need to handle queries in loop vertices (the periodic handouts)
}
}
vis.clear();
vis.resize(n + 1);
for(int i = 1; i <= n; ++i){
if(loop_id[i] == 0 || vis[i]) continue;
vector<array<ll, 2>> QQ; // queries fixed at V
ll dst = 0;
ll SZ = cycle_size[loop_id[i]];
int V = i;
for(int x = V; !vis[x]; x = go[x][0]){
for(auto [t, idx]: Q[x]){
QQ.pb({t - (dst == 0 ? SZ : dst), idx});
}
vis[x] = 1;
dst += go[x][1];
}
oset MD; // contains modulo SZ's
sort(all(QQ));
ll sum = 0;
int ptr = 0;
auto it = T[i].begin();
for(auto [t, idx]: QQ){
// while(it != T[i].end() && (*it).ff <= t){
// MD.insert({((*it).ff + SZ) % SZ, ptr});
// sum += - ((*it).ff / SZ);
// ++ptr;
// ++it;
// }
int x = (MD.order_of_key(pair<ll, int>{((t + SZ) % SZ) + 1, -1}));
// ANS[idx] += ptr * (t / SZ) + sum + (MD.order_of_key(pair<ll, int>{((t + SZ) % SZ) + 1, -1}));
}
}
for(int i = 1; i <= q; ++i){
cout << ANS[i] << '\n';
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |