#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname ""
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
ll a[200001],b[200001];
ll n,m,l,c,q;
vector<pair<ll,ll>> adj[500001],adjrev[500001];
ll vis[500001];
ll dist[500001];
ll cnt;
vector<vector<pair<ll,ll>>> compart;
vector<vector<ll>> pref;
vector<ll> len;
ll num[500001];
ll insub[500001];
bool inloop[500001];
ll root;
void dfs(ll u){
if(root) return ;
if(vis[u]){
root=u;
return ;
}
vis[u]=1;
for(auto [v,w]:adj[u]){
dfs(v);
}
}
void dfs1(ll u=root,ll d=0){
vis[u]=1;
num[u]=cnt;
if(u>n){
insub[u]=1;
compart[cnt].push_back({d%len[cnt],d/len[cnt]});
}
for(auto [v,w]:adjrev[u]){
if(v==root) continue;
dfs1(v,d+w);
insub[u]+=insub[v];
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//frep;
cin>>n>>m>>l>>c;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
for(int i=1;i<=n;i++){
ll t=((a[i]-c)%l+l)%l;
ll pos=upper_bound(a+1,a+n+1,t)-a-1;
if(pos==0) pos=n;
//if(i==j) continue;
ll v=((a[i]-a[pos])%l+l)%l;
ll cost=(c-v+l-1)/l*l+v;
// cout<<i<<' '<<pos<<' '<<mn<<ntr;
adj[i].push_back({pos,cost});
adjrev[pos].push_back({i,cost});
}
for(int i=1;i<=m;i++){
ll v=upper_bound(a+1,a+n+1,b[i])-a-1;
if(v==0) v=n;
ll cost=((b[i]-a[v])%l+l)%l;
adj[i+n].push_back({v,cost});
adjrev[v].push_back({i+n,cost});
// cout<<i<<' '<<v<<' '<<cost<<ntr;
}
compart.push_back({});
pref.push_back({});
len.push_back(0);
for(int i=1;i<=m;i++){
if(!vis[i+n]) root=0,dfs(i+n);
cnt++;
compart.push_back({});
pref.push_back({});
ll p=root;
dist[root]=0;
while(true){
inloop[p]=1;
auto [v,w]=adj[p][0];
if(v==root){
len.push_back(dist[p]+w);
break;
}
dist[v]=dist[p]+w;
p=v;
}
dfs1();
sort(compart[cnt].begin(),compart[cnt].end());
pref[cnt].push_back(compart[cnt][0].second);
for(int i=1;i<compart[cnt].size();i++){
pref[cnt].push_back(pref[cnt].back()+compart[cnt][i].second);
}
}
cin>>q;
for(int i=1;i<=q;i++){
ll u,t;
cin>>u>>t;
t-=dist[u];
if(!inloop[u]){
cout<<insub[u]<<ntr;
continue;
}
else{
ll ans=0;//insub[u];
ll p=t/len[num[u]];
ll q=t%len[num[u]];
ll lo=0,hi=compart[num[u]].size()-1,pos=-1;
while(lo<=hi){
ll mid=(lo+hi)/2;
if(compart[cnt][mid].first<=q) pos=mid,lo=mid+1;
else hi=mid-1;
}
ans+=(compart[num[u]].size()-1)*p+pref[num[u]].back();
ans+=p+1;
cout<<ans<<ntr;
}
}
}
Compilation message
harvest.cpp: In function 'int main()':
harvest.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i=1;i<compart[cnt].size();i++){
| ~^~~~~~~~~~~~~~~~~~~~
harvest.cpp:110:49: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
110 | ll lo=0,hi=compart[num[u]].size()-1,pos=-1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33360 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
25160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
520 ms |
290308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33360 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
25160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
