#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (ll x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll n,m,l,k,q;
ll arr[200005];
ll brr[200005];
vector<ll> pos;
ii nxt[200005];
bool vis[200005];
bool onstk[200005];
ll cycl[200005];
void dfs(int i){
vis[i]=true;
onstk[i]=true;
if (!vis[nxt[i].fi]) dfs(nxt[i].fi);
else if (onstk[nxt[i].fi]){
ll curr=i;
ll len=0;
do{
len+=nxt[curr].se;
curr=nxt[curr].fi;
} while (curr!=i);
do{
cycl[curr]=len;
curr=nxt[curr].fi;
} while (curr!=i);
}
onstk[i]=false;
}
vector<ll> t[3005];
int main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cin>>n>>m>>l>>k;
rep(x,0,n) cin>>arr[x];
rep(x,0,m) cin>>brr[x];
rep(x,0,n) arr[x]=l-arr[x];
rep(x,0,m) brr[x]=l-brr[x];
reverse(arr,arr+n);
reverse(brr,brr+m);
rep(z,0,2) rep(x,0,n) pos.pub(arr[x]+z*l);
rep(x,0,n){
auto iter=lb(all(pos),(arr[x]+k)%l)-pos.begin();
nxt[x]=ii(iter%n,(pos[iter]-(arr[x]+k)%l)+k);
}
rep(x,0,n){
//cout<<x<<" "<<arr[x]<<" "<<nxt[x].fi<<" "<<nxt[x].se<<endl;
}
memset(cycl,-1,sizeof(cycl));
rep(x,0,n) if (!vis[x]){
dfs(x);
}
//rep(x,0,n) cout<<cycl[x]<<" "; cout<<endl;
rep(x,0,m){
auto iter=lb(all(pos),brr[x])-pos.begin();
int curr=iter%n;
int ctime=pos[iter]-brr[x];
//cout<<"debug: "<<brr[x]<<" "<<curr<<" "<<ctime<<endl;
memset(vis,false,sizeof(vis));
do{
vis[curr]=true;
t[curr].pub(ctime);
//cout<<curr<<" "<<ctime<<endl;
ctime+=nxt[curr].se;
curr=nxt[curr].fi;
} while (!vis[curr]);
}
cin>>q;
ll a,b;
while (q--){
cin>>a>>b;
a=n-a;
assert(0<=a && a<n);
ll ans=0;
if (cycl[a]==-1){
for (auto &it:t[a]) if (it<=b) ans++;
}
else{
for (auto &it:t[a]) if (it<=b) ans+=(b-it)/cycl[a]+1;
}
cout<<ans<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5025 ms |
4516 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
