#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,tsz;
int a[200005],b[200005],prv[200005],deg[200005],rt[200005],fenw[200005],dfn[200005],dfo[200005],cnt[10000005],ls[10000005],rs[10000005],root[200005];
ll d[200005],sum[10000005];
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;}
ll divb(ll x,ll y){return x>=0?x-x%y:x-((y+(x%y))%y);}
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;
}
/*void modifyy(int&id,int l,int r,int p,ll v){
if(!id) id=++tsz,cnt[id]=sum[id]=ls[id]=rs[id]=0;
sum[id]+=v;
cnt[id]++;
if(l==r) return;
int mid=(l+r)/2;
if(p<=mid) modifyy(ls[id],l,mid,p,v);
else modifyy(rs[id],mid+1,r,p,v);
}
void modifyx(int x,int y,ll v){
for(;x<200000;x|=(x+1)) modifyy(root[x],0,200000,y,v);
}
pair<ll,int> queryy(int id,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return mp(sum[id],cnt[id]);
int mid=(l+r)/2;
if(qr<=mid) return queryy(ls[id],l,mid,ql,qr);
else if(ql>mid) return queryy(rs[id],mid+1,r,ql,qr);
pair<ll,int> lv=queryy(ls[id],l,mid,ql,qr);
pair<ll,int> rv=queryy(rs[id],mid+1,r,ql,qr);
return mp(lv.fi+rv.fi,lv.se+rv.se);
}
pair<ll,int> queryx(int x1,int x2,int y1,int y2){
pair<ll,int> ret=mp(0ll,0);
for(int x=x2;x>=0;x=(x&(x+1))-1){
pair<ll,int> f=queryy(root[x],0,200000,y1,y2);
ret.fi+=f.fi;
ret.se+=f.se;
}
for(int x=x1-1;x>=0;x=(x&(x+1))-1){
pair<ll,int> f=queryy(root[x],0,200000,y1,y2);
ret.fi-=f.fi;
ret.se-=f.se;
}
return ret;
}
void clrx(int x){
for(;x<200000;x|=(x+1)) root[x]=0;
}*/
ll S[6005][6005];
int C[6005][6005];
void modifyx(int x,int y,ll v,int c){
for(int i=x;i<6005;i|=(i+1)){
for(int j=y;j<6005;j|=(j+1)){
S[i][j]+=v;
C[i][j]+=c;
}
}
}
pair<ll,int> query(int x,int y){
pair<ll,int> ret=mp(0ll,0);
for(int i=x;i>=0;i=(i&(i+1))-1){
for(int j=y;j>=0;j=(j&(j+1))-1){
ret.fi+=S[i][j];
ret.se+=C[i][j];
}
}
return ret;
}
pair<ll,int> queryx(int x1,int x2,int y1,int y2){
pair<ll,int> ret=query(x2,y2);
ret.fi-=query(x2,y1-1).fi;
ret.se-=query(x2,y1-1).se;
ret.fi-=query(x1-1,y2).fi;
ret.se-=query(x1-1,y2).se;
ret.fi+=query(x1-1,y1-1).fi;
ret.se+=query(x1-1,y1-1).se;
return ret;
}
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();
d[0]=0;
for(int i=1;i<sz;i++){
ll w=calc(a[f[i]]<=a[f[i-1]]?a[f[i-1]]-a[f[i]]:a[f[i-1]]+l-a[f[i]]);
d[i]=d[i-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);
vector<ll> xs1,xs2;
for(int i=0;i<sz;i++){
for(auto&p:my[f[i]]){
xs1.pb(d[i]-p);
xs2.pb(d[i]-p-divb(d[i]-p,len));
}
for(auto&p:qs[f[i]]){
xs1.pb(-(p.fi-d[i]));
xs2.pb(len-(p.fi-d[i]-divb(p.fi-d[i],len)));
}
}
sort(xs1.begin(),xs1.end());
xs1.erase(unique(xs1.begin(),xs1.end()),xs1.end());
sort(xs2.begin(),xs2.end());
xs2.erase(unique(xs2.begin(),xs2.end()),xs2.end());
int sz1=(int)xs1.size(),sz2=(int)xs2.size();
vector<ll> vec;
for(int i=0;i<sz;i++){
for(auto&p:my[f[i]]){
int idx1=(int)(lower_bound(xs1.begin(),xs1.end(),d[i]-p)-xs1.begin());
int idx2=(int)(lower_bound(xs2.begin(),xs2.end(),d[i]-p-divb(d[i]-p,len))-xs2.begin());
modifyx(idx1,idx2,divb(d[i]-p,len),1);
vec.pb(d[i]-p);
}
for(auto&p:qs[f[i]]){
int idx1=(int)(lower_bound(xs1.begin(),xs1.end(),-(p.fi-d[i]))-xs1.begin());
int idx2=(int)(lower_bound(xs2.begin(),xs2.end(),len-(p.fi-d[i]-divb(p.fi-d[i],len)))-xs2.begin());
pair<ll,int> tmp=queryx(idx1,sz1-1,0,sz2-1);
ll s=(tmp.se*1ll*divb(p.fi-d[i],len)*0ll)/len+tmp.se+tmp.fi/len;
for(auto&pp:vec){
if(pp+(p.fi-d[i])<0) continue;
s+=(divb(p.fi-d[i],len))/len;
}
ans[p.se]+=s+queryx(idx1,sz1-1,idx2,sz2-1).se;
}
}
//clrx(root,0,sz1-1,0,sz2-1);
while(tsz){
ls[tsz]=rs[tsz]=sum[tsz]=cnt[tsz]=0;
tsz--;
}
for(int i=0;i<sz;i++){
for(auto&p:my[f[i]]){
int idx1=(int)(lower_bound(xs1.begin(),xs1.end(),d[i]-p)-xs1.begin());
int idx2=(int)(lower_bound(xs2.begin(),xs2.end(),d[i]-p-divb(d[i]-p,len))-xs2.begin());
modifyx(idx1,idx2,-divb(d[i]-p,len),-1);
}
}
for(int i=0;i<sz;i++){
for(int j=0;j<i;j++){
for(auto&p:my[f[i]]){
for(auto&pp:qs[f[j]]){
ans[pp.se]+=max(0ll,pp.fi-(i<=j?d[j]-d[i]:d[j]+len-d[i])-p+len)/len;
}
}
}
}
}
for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
33628 KB |
Output is correct |
| 2 |
Correct |
16 ms |
52316 KB |
Output is correct |
| 3 |
Correct |
133 ms |
213936 KB |
Output is correct |
| 4 |
Correct |
42 ms |
223764 KB |
Output is correct |
| 5 |
Correct |
35 ms |
249616 KB |
Output is correct |
| 6 |
Correct |
34 ms |
249780 KB |
Output is correct |
| 7 |
Correct |
33 ms |
249716 KB |
Output is correct |
| 8 |
Correct |
32 ms |
249228 KB |
Output is correct |
| 9 |
Correct |
31 ms |
249172 KB |
Output is correct |
| 10 |
Correct |
31 ms |
249280 KB |
Output is correct |
| 11 |
Correct |
30 ms |
249304 KB |
Output is correct |
| 12 |
Correct |
77 ms |
279784 KB |
Output is correct |
| 13 |
Correct |
88 ms |
221700 KB |
Output is correct |
| 14 |
Correct |
60 ms |
127328 KB |
Output is correct |
| 15 |
Correct |
34 ms |
249596 KB |
Output is correct |
| 16 |
Correct |
33 ms |
249620 KB |
Output is correct |
| 17 |
Correct |
32 ms |
249420 KB |
Output is correct |
| 18 |
Correct |
31 ms |
249368 KB |
Output is correct |
| 19 |
Correct |
31 ms |
249580 KB |
Output is correct |
| 20 |
Correct |
31 ms |
249564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
72 ms |
46460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
33628 KB |
Output is correct |
| 2 |
Correct |
16 ms |
52316 KB |
Output is correct |
| 3 |
Correct |
133 ms |
213936 KB |
Output is correct |
| 4 |
Correct |
42 ms |
223764 KB |
Output is correct |
| 5 |
Correct |
35 ms |
249616 KB |
Output is correct |
| 6 |
Correct |
34 ms |
249780 KB |
Output is correct |
| 7 |
Correct |
33 ms |
249716 KB |
Output is correct |
| 8 |
Correct |
32 ms |
249228 KB |
Output is correct |
| 9 |
Correct |
31 ms |
249172 KB |
Output is correct |
| 10 |
Correct |
31 ms |
249280 KB |
Output is correct |
| 11 |
Correct |
30 ms |
249304 KB |
Output is correct |
| 12 |
Correct |
77 ms |
279784 KB |
Output is correct |
| 13 |
Correct |
88 ms |
221700 KB |
Output is correct |
| 14 |
Correct |
60 ms |
127328 KB |
Output is correct |
| 15 |
Correct |
34 ms |
249596 KB |
Output is correct |
| 16 |
Correct |
33 ms |
249620 KB |
Output is correct |
| 17 |
Correct |
32 ms |
249420 KB |
Output is correct |
| 18 |
Correct |
31 ms |
249368 KB |
Output is correct |
| 19 |
Correct |
31 ms |
249580 KB |
Output is correct |
| 20 |
Correct |
31 ms |
249564 KB |
Output is correct |
| 21 |
Runtime error |
72 ms |
46460 KB |
Execution killed with signal 11 |
| 22 |
Halted |
0 ms |
0 KB |
- |
