//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
struct BIT{
vector<int> bit;
int n;
BIT(int N){
n=N;
bit=vector<int>(n,0);
}
void update(int pos,int val){
for(;pos<n;pos+=(pos&-pos)){
bit[pos]+=val;
}
}
int query(int pos){
int ans=0;
for(;pos>0;pos-=(pos&-pos)){
ans+=bit[pos];
}
return ans;
}
};
const int mxn=200000+5;
const int inf=1e18;
int a[mxn];
int b[mxn];
int nxt[mxn*2];
bool visited[mxn*2];
bool is_cycle[mxn*2];
vector<pair<int,ll>> adj[mxn*2];
int belong[mxn*2];
ll depth[mxn*2];
ll d[mxn*2];
ll sum[mxn*2];
int rev[mxn*2];
int st[mxn*2],en[mxn*2];
vector<pair<int,int>> sta;
vector<pair<int,int>> js[mxn];
vector<pair<pair<int,int>,int>> is[mxn];
vector<vector<ll>> pre;
int n,m,l,c;
int timer=0;
void dfs(int id,int p,int v){
st[v]=++timer;
if(v>=n){
sta.push_back({depth[v]-pre[id][rev[p]],p});
}
for(auto u:adj[v]){
if(is_cycle[u.f]) continue;
depth[u.f]=depth[v]+u.s;
dfs(id,p,u.f);
}
en[v]=timer;
}
signed main() {_
cin>>n>>m>>l>>c;
ll C=c;
c%=l;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<m;i++){
cin>>b[i];
}
for(int i=0;i<n;i++){
int pos=upper_bound(a,a+n,(a[i]-c+l)%l)-a-1;
if(pos==-1) pos=n-1;
nxt[i]=pos;
d[i]=((a[i]-c+l)%l-a[pos]+l)%l+C;
}
for(int i=0;i<m;i++){
int pos=upper_bound(a,a+n,b[i])-a-1;
if(pos==-1) pos=n-1;
nxt[i+n]=pos;
d[i+n]=(b[i]-a[pos]+l)%l;
}
for(int i=0;i<n+m;i++){
adj[nxt[i]].push_back({i,d[i]});
}
vector<vector<int>> cycle;
for(int i=0;i<n+m;i++){
if(visited[i]) continue;
int x=i;
vector<int> tmp;
while(!visited[x]){
visited[x]=true;
tmp.push_back(x);
x=nxt[x];
}
bool ok=false;
for(auto v:tmp){
ok|=(v==x);
is_cycle[v]=ok;
}
if(!ok) continue;
vector<int> curcycle;
for(auto v:tmp){
if(is_cycle[v]){
curcycle.push_back(v);
belong[v]=(int)cycle.size();
}
}
cycle.push_back(curcycle);
vector<ll> dis;
dis.push_back(0);
for(int i=1;i<(int)curcycle.size();i++){
dis.push_back(dis.back()+d[curcycle[i-1]]);
}
pre.push_back(dis);
for(int i=0;i<(int)curcycle.size();i++){
rev[curcycle[i]]=i;
}
}
for(int i=0;i<(int)cycle.size();i++){
int cnt=0;
for(auto v:cycle[i]){
sta.clear();
dfs(i,v,v);
js[i].insert(js[i].end(),all(sta));
sum[i]+=d[v];
}
}
int q;
cin>>q;
vector<pair<ll,pair<int,int>>> qys;
vector<int> res(q);
for(int i=0;i<q;i++){
int v;
ll t;
cin>>v>>t;
v--;
if(!is_cycle[v]){
qys.push_back({t+depth[v],{i,v}});
continue;
}
int id=belong[v];
is[id].push_back({{t-pre[id][rev[v]],v},i});
}
// tree
{
for(int i=n;i<n+m;i++){
qys.push_back({depth[i],{-1,i}});
}
sort(qys.begin(),qys.end());
BIT T(mxn);
for(auto query:qys){
int id=query.s.f;
int v=query.s.s;
if(id==-1){
T.update(st[v],1);
}
else{
//res[id]=T.query(en[v])-T.query(st[v]-1);
assert(res[id]>=0);
}
}
}
// cycle
for(int t=0;t<(int)cycle.size();t++){
{
vector<pair<pair<int,int>,int>> vec;
vector<int> xs;
xs.push_back(-inf);
for(auto v:is[t]){
int a=v.f.f/sum[t];
assert(sum[t]!=0);
if(a*sum[t]>v.f.f) a--;
int b=v.f.f-a*sum[t];
xs.push_back(b);
vec.push_back({{a,v.s},b});
}
for(auto v:js[t]){
int a=v.f/sum[t];
assert(sum[t]!=0);
if(a*sum[t]>v.f) a--;
int b=v.f-a*sum[t];
xs.push_back(b);
vec.push_back({{a,-1},b});
}
sort(all(xs));
xs.resize(unique(all(xs))-xs.begin());
sort(all(vec));
int sum2=0;
int cnt=0;
BIT T(xs.size());
for(auto v:vec){
int pos=lower_bound(all(xs),v.s)-xs.begin();
if(v.f.s==-1){
sum2+=v.f.f;
cnt++;
T.update(pos,1);
}
else{
int i=v.f.s;
res[i]+=cnt*v.f.f;
res[i]-=sum2;
res[i]+=T.query(pos);
}
}
}
{
vector<pair<pair<int,int>,int>> vec;
vector<int> xs;
xs.push_back(-inf);
for(auto v:is[t]){
xs.push_back(v.f.f);
vec.push_back({{rev[v.f.s],v.s},v.f.f});
}
for(auto v:js[t]){
xs.push_back(v.f);
vec.push_back({{rev[v.s],-1},v.f});
}
sort(all(xs));
xs.resize(unique(all(xs))-xs.begin());
sort(all(vec));
reverse(all(vec));
BIT T(xs.size());
for(auto v:vec){
int pos=lower_bound(all(xs),v.s)-xs.begin();
if(v.f.s==-1){
T.update(pos,1);
}
else{
int i=v.f.s;
res[i]-=T.query(pos);
}
}
}
}
for(int i=0;i<q;i++){
//assert(res[i]>=0);
cout<<res[i]<<'\n';
}
return 0;
}
//maybe its multiset not set
//yeeorz
//laborz
/*
1 1 2 5
0
1
10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
*/
Compilation message
harvest.cpp: In function 'int main()':
harvest.cpp:135:13: warning: unused variable 'cnt' [-Wunused-variable]
135 | int cnt=0;
| ^~~
harvest.cpp: In function 'void setIO(std::string)':
harvest.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
39260 KB |
Output is correct |
| 2 |
Correct |
11 ms |
40028 KB |
Output is correct |
| 3 |
Correct |
12 ms |
40028 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
39524 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
191 ms |
58328 KB |
Output is correct |
| 2 |
Incorrect |
130 ms |
63472 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
39260 KB |
Output is correct |
| 2 |
Correct |
11 ms |
40028 KB |
Output is correct |
| 3 |
Correct |
12 ms |
40028 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
39524 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
