#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pli pair<ll,int>
#define pb push_back
const int N=400050;
int a[N],b[N],go[N],len[N*2],was[N],csz,on_chn[N],n,m,l,c,h,lid[N*2],rid[N*2],tid;
ll dep[N*2],chn_len[N],my_chn_len[N],ans[N];
vector<int> E[N*2];
void DFS(int u,ll cl){
dep[u]+=len[u];
//printf("%i dep %lld\n",u,dep[u]);
lid[u]=tid+1;
if(u>n&&u<=h||u>h+n&&u<=2*h)tid++,my_chn_len[tid]=cl;
for(int v:E[u])if(!on_chn[v])dep[v]=dep[u],DFS(v,cl);
rid[u]=tid;
}
const int M=2*N;
int ls[M],rs[M],tsz,root,sz[M];
multiset<int> ost[M];
ll sub[M];
void Set(int&c,int ss,int se,int qi,ll x,int y){
if(!c)c=++tsz;
sz[c]++;
sub[c]+=x;
ost[c].insert(y);
if(ss==se)return;
int mid=ss+se>>1;
if(qi<=mid)Set(ls[c],ss,mid,qi,x,y);
else Set(rs[c],mid+1,se,qi,x,y);
}
int GetCnt(int c,int ss,int se,int qs,int qe){
if(qs>qe||qs>se||ss>qe)return 0;
if(qs<=ss&&qe>=se)return sz[c];
int mid=ss+se>>1;
return GetCnt(ls[c],ss,mid,qs,qe)+GetCnt(rs[c],mid+1,se,qs,qe);
}
ll Get(int c,int ss,int se,int qs,int qe){
if(qs>qe||qs>se||ss>qe)return 0;
if(qs<=ss&&qe>=se)return sub[c];
int mid=ss+se>>1;
return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
int Lo(int c,int ss,int se,int qs,int qe,int y){
if(qs>qe||qs>se||ss>qe)return 0;
if(qs<=ss&&qe>=se){
int ans=0;
for(auto it:ost[c]){
if(it>y)break;
ans++;
}
return ans;
}
int mid=ss+se>>1;
return Lo(ls[c],ss,mid,qs,qe,y)+Lo(rs[c],mid+1,se,qs,qe,y);
}
void Add(pli p){
Set(root,1,tid,p.second,p.first/my_chn_len[p.second],p.first%my_chn_len[p.second]);
}
int Count(int l,int r){return GetCnt(root,1,tid,l,r);}
ll Get(int l,int r){return Get(root,1,tid,l,r);}
int Lo(int l,int r,int y){return Lo(root,1,tid,l,r,y);}
int q,V[N],ord[N];
ll T[N];
int main(){
scanf("%i %i %i %i",&n,&m,&l,&c);
for(int i=1;i<=n;i++)scanf("%i",&a[i]),a[i]=l-a[i];
reverse(a+1,a+1+n);
for(int i=1;i<=n;i++)a[i+n]=a[i]+l;
for(int i=1;i<=n;i++){
int j=lower_bound(a+i,a+i+1+n,a[i]+c%l)-a;
assert(j<=2*n);
len[i]=c/l*l+a[j]-a[i];
if(j>n)j-=n;
go[i]=j;
}
for(int i=1;i<=m;i++){
scanf("%i",&b[i]);
b[i]=l-b[i];
int j=lower_bound(a+1,a+1+2*n,b[i])-a;
len[n+i]=a[j]-b[i];
go[n+i]=j>n?j-n:j;
}
h=n+m;
for(int i=1;i<=h;i++){
E[go[i]].pb(i);
E[go[i]+h].pb(i+h);
len[i+h]=len[i];
//printf("(%i -> %i) %i\n",i,go[i],len[i]);
}
for(int i=1;i<=n;i++)if(!was[i]){
int j=i;csz++;
while(!was[j])was[j]=csz,j=go[j];
if(was[j]!=csz)continue;
int k=j;
vector<int> chn;
//printf("[ ");
do{
chn.pb(k);
//printf("%i ",k);
on_chn[k]=on_chn[k+h]=1;
chn_len[csz]+=len[k];
k=go[k];
}while(k!=j);
//printf(" ]\n");
reverse(chn.begin(),chn.end());
ll sum=0;
for(int k:chn){
dep[k]=sum;
DFS(k,chn_len[csz]);
sum+=len[k];
}
for(int k:chn){
dep[k+h]=sum;
DFS(k+h,chn_len[csz]);
sum+=len[k];
}
}
vector<pli> leaf;
for(int i=n+1;i<=h;i++){
leaf.pb({dep[i],lid[i]});
leaf.pb({dep[i+h],lid[i+h]});
}
sort(leaf.begin(),leaf.end());
scanf("%i",&q);
for(int i=1;i<=q;i++){
scanf("%i %lld",&V[i],&T[i]);
V[i]=n-V[i]+1;
T[i]+=dep[V[i]];
ord[i]=i;
}
sort(ord+1,ord+1+q,[&](int i,int j){return T[i]<T[j];});
for(int z=1,j=0;z<=q;z++){
int i=ord[z];
while(j<leaf.size()&&leaf[j].first<=T[i])Add(leaf[j]),j++;
if(on_chn[V[i]]){
int L=lid[V[i]],R=lid[V[i]+h]-1;
int cnt=Count(L,R);
ll now=cnt*(T[i]/chn_len[was[V[i]]])-Get(L,R);
now+=Lo(L,R,T[i]%chn_len[was[V[i]]]);
ans[i]=now;
}else{
ans[i]=Count(lid[V[i]],rid[V[i]]);
}
}
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
Compilation message
harvest.cpp: In function 'void DFS(int, long long int)':
harvest.cpp:14:8: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
14 | if(u>n&&u<=h||u>h+n&&u<=2*h)tid++,my_chn_len[tid]=cl;
| ~~~^~~~~~
harvest.cpp: In function 'void Set(int&, int, int, int, long long int, int)':
harvest.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | int mid=ss+se>>1;
| ~~^~~
harvest.cpp: In function 'int GetCnt(int, int, int, int, int)':
harvest.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid=ss+se>>1;
| ~~^~~
harvest.cpp: In function 'long long int Get(int, int, int, int, int)':
harvest.cpp:41:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int mid=ss+se>>1;
| ~~^~~
harvest.cpp: In function 'int Lo(int, int, int, int, int, int)':
harvest.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid=ss+se>>1;
| ~~^~~
harvest.cpp: In function 'int main()':
harvest.cpp:135:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | while(j<leaf.size()&&leaf[j].first<=T[i])Add(leaf[j]),j++;
| ~^~~~~~~~~~~~
harvest.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
66 | scanf("%i %i %i %i",&n,&m,&l,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:67:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
67 | for(int i=1;i<=n;i++)scanf("%i",&a[i]),a[i]=l-a[i];
| ~~~~~^~~~~~~~~~~~
harvest.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
78 | scanf("%i",&b[i]);
| ~~~~~^~~~~~~~~~~~
harvest.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
125 | scanf("%i",&q);
| ~~~~~^~~~~~~~~
harvest.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
127 | scanf("%i %lld",&V[i],&T[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
56960 KB |
Output is correct |
| 2 |
Correct |
65 ms |
61772 KB |
Output is correct |
| 3 |
Correct |
145 ms |
61860 KB |
Output is correct |
| 4 |
Correct |
56 ms |
61304 KB |
Output is correct |
| 5 |
Correct |
59 ms |
61816 KB |
Output is correct |
| 6 |
Correct |
63 ms |
61816 KB |
Output is correct |
| 7 |
Correct |
56 ms |
61944 KB |
Output is correct |
| 8 |
Correct |
55 ms |
61688 KB |
Output is correct |
| 9 |
Correct |
49 ms |
59640 KB |
Output is correct |
| 10 |
Correct |
55 ms |
61688 KB |
Output is correct |
| 11 |
Correct |
48 ms |
59640 KB |
Output is correct |
| 12 |
Correct |
50 ms |
59768 KB |
Output is correct |
| 13 |
Incorrect |
142 ms |
61816 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3221 ms |
69448 KB |
Output is correct |
| 2 |
Runtime error |
357 ms |
164640 KB |
Execution killed with signal 8 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
56960 KB |
Output is correct |
| 2 |
Correct |
65 ms |
61772 KB |
Output is correct |
| 3 |
Correct |
145 ms |
61860 KB |
Output is correct |
| 4 |
Correct |
56 ms |
61304 KB |
Output is correct |
| 5 |
Correct |
59 ms |
61816 KB |
Output is correct |
| 6 |
Correct |
63 ms |
61816 KB |
Output is correct |
| 7 |
Correct |
56 ms |
61944 KB |
Output is correct |
| 8 |
Correct |
55 ms |
61688 KB |
Output is correct |
| 9 |
Correct |
49 ms |
59640 KB |
Output is correct |
| 10 |
Correct |
55 ms |
61688 KB |
Output is correct |
| 11 |
Correct |
48 ms |
59640 KB |
Output is correct |
| 12 |
Correct |
50 ms |
59768 KB |
Output is correct |
| 13 |
Incorrect |
142 ms |
61816 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
