#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
ll readint(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,l,c,q,T;
int a[200005],b[200005],prv[200005],deg[200005],rt[200005],fenw[200005],dfn[200005],dfo[200005];
ll d[200005];
vector<pair<ll,int>> qs[200005];
vector<array<ll,4>> ev;
vector<ll> my[200005];
ll ans[200005];
vector<int> topo,ch[200005];
bool oncyc[200005];
ll calc(ll x){return x>=c?x:((c-x+l-1)/l)*1ll*l+x;}
int getprv(int x){
int d=c%l;
if(a[1]<=x-d){
int l=1,r=n,p=1;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]<=x-d) l=mid+1,p=mid;
else r=mid-1;
}
return p;
}else{
int l=1,r=n,p=1;
while(l<=r){
int mid=(l+r)/2;
if(x+::l-a[mid]>=d) l=mid+1,p=mid;
else r=mid-1;
}
return p;
}
}
void change(int p,int v){
for(;p<200005;p|=p+1) fenw[p]+=v;
}
int ask(int p){
int v=0;
for(;p>=0;p=(p&(p+1))-1) v+=fenw[p];
return v;
}
void dfs1(int x,ll d){
dfn[x]=++T;
for(auto&p:my[x]) ev.pb({-d+p,0,dfn[x],0});
for(auto&p:qs[x]) ev.pb({p.fi+d,1,x,p.se});
for(auto&p:my[x]) my[rt[x]].pb(p+d);
for(int v:ch[x]){
rt[v]=rt[x];
ll w=calc(a[x]<=a[v]?a[v]-a[x]:a[v]+l-a[x]);
dfs1(v,d+w);
}
dfo[x]=T;
}
int main(){
n=readint(); m=readint(); l=readint(); c=readint();
for(int i=1;i<=n;i++) a[i]=readint();
for(int i=1;i<=m;i++) b[i]=readint();
q=readint();
for(int i=1;i<=q;i++){
int v=readint();
ll t=readint();
qs[v].pb(mp(t,i));
}
for(int i=1;i<=n;i++) prv[i]=getprv(a[i]);
for(int i=1;i<=m;i++){
int idx;
if(a[1]<=b[i]){
int l=1,r=n;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]<=b[i]) idx=mid,l=mid+1;
else r=mid-1;
}
}else idx=n;
my[idx].pb((b[i]-a[idx]+l)%l);
}
for(int i=1;i<=n;i++) deg[prv[i]]++;
for(int i=1;i<=n;i++) if(deg[i]==0) topo.pb(i);
for(int i=0;i<(int)topo.size();i++){
int v=topo[i];
deg[prv[v]]--;
if(deg[prv[v]]==0) topo.pb(prv[v]);
}
for(int i=1;i<=n;i++) oncyc[i]=true;
for(int i:topo) oncyc[i]=false;
for(int i=1;i<=n;i++) ch[prv[i]].pb(i);
for(int i=1;i<=n;i++){
if(oncyc[i]||!oncyc[prv[i]]) continue;
rt[i]=prv[i];
ll w=calc(a[prv[i]]<=a[i]?a[i]-a[prv[i]]:a[i]+l-a[prv[i]]);
T=0;
ev.clear();
dfs1(i,w);
sort(ev.begin(),ev.end());
for(auto&p:ev){
if(p[1]==0){
change(p[2],1);
}else{
ans[p[3]]=ask(dfo[p[2]])-ask(dfn[p[2]]-1);
}
}
for(auto&p:ev) if(p[1]==0) change(p[2],-1);
}
for(int i=1;i<=n;i++){
if(!oncyc[i]) continue;
vector<int> f;
int ver=i;
while(oncyc[ver]){
f.pb(ver);
oncyc[ver]=false;
ver=prv[ver];
}
int sz=(int)f.size();
vector<int> tmp=f;
for(int i=0;i<sz;i++){
f.clear();
int ver=tmp[i];
for(int j=0;j<sz;j++) f.pb(ver),ver=prv[ver];
d[0]=0;
for(int j=1;j<sz;j++){
ll w=calc(a[f[j]]<=a[f[j-1]]?a[f[j-1]]-a[f[j]]:a[f[j-1]]+l-a[f[j]]);
d[j]=d[j-1]+w;
}
ll len=d[sz-1]+calc(a[f[0]]<=a[f.back()]?a[f.back()]-a[f[0]]:a[f.back()]+l-a[f[0]]);
if(f.size()==1) len=calc(l);
for(int j=0;j<sz;j++){
for(auto&p:my[f[0]]){
for(auto&pp:qs[f[j]]){
ans[pp.se]+=max(0ll,pp.fi-d[j]-p+len)/len;
}
}
}
}
}
for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
21060 KB |
Output is correct |
| 2 |
Correct |
6 ms |
21096 KB |
Output is correct |
| 3 |
Correct |
87 ms |
21500 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
23644 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5036 ms |
28872 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
21060 KB |
Output is correct |
| 2 |
Correct |
6 ms |
21096 KB |
Output is correct |
| 3 |
Correct |
87 ms |
21500 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
23644 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
