//#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);
}
const int mxn=6000+5;
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];
vector<pair<int,int>> st;
vector<pair<int,int>> qs[mxn];
vector<vector<ll>> pre;
int n,m,l,c;
void dfs(int p,int v){
if(v>=n){
st.push_back({v,p});
}
for(auto u:adj[v]){
if(is_cycle[u.f]) continue;
depth[u.f]=depth[v]+u.s;
dfs(p,u.f);
}
}
int dfs_ans(int p,int v,ll t){
if(v>=n){
if(depth[v]-depth[p]<=t) return 1;
else return 0;
}
int ans=0;
for(auto u:adj[v]){
ans+=dfs_ans(p,u.f,t);
}
return ans;
}
signed main() {_
cin>>n>>m>>l>>c;
c%=l;
assert(l==2);
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++){
if(a[i]-c>=a[0]){
nxt[i]=upper_bound(a,a+n,a[i]-c)-a-1;
d[i]=a[i]-a[nxt[i]];
}
else{
int val=(a[i]-c+l);
nxt[i]=upper_bound(a,a+n,val)-a-1;
d[i]=a[i]+l-a[nxt[i]];
//cout<<"sir "<<i<<' '<<nxt[i]<<'\n';
}
if(d[i]==0) d[i]=l;
}
for(int i=0;i<m;i++){
if(b[i]>=a[0]){
nxt[i+n]=upper_bound(a,a+n,b[i])-a-1;
d[i+n]=b[i]-a[nxt[i+n]];
}
else{
int val=(b[i]+l);
nxt[i+n]=upper_bound(a,a+n,val)-a-1;
d[i+n]=b[i]+l-a[nxt[i+n]];
}
}
for(int i=0;i<n+m;i++){
//cout<<nxt[i]<<' '<<d[i]<<'\n';
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);
}
//return 0;
for(int i=0;i<(int)cycle.size();i++){
int cnt=0;
for(auto v:cycle[i]){
st.clear();
dfs(v,v);
qs[i].insert(qs[i].end(),all(st));
sum[i]+=d[v];
rev[v]=cnt++;
//cout<<v<<' ';
}
//cout<<'\n';
}
//return 0;
int q;
cin>>q;
for(int i=0;i<q;i++){
int v;
ll t;
cin>>v>>t;
v--;
if(!is_cycle[v]){
//return 0;
cout<<dfs_ans(v,v,t)<<'\n';
continue;
}
//continue;
int id=belong[v];
ll ans=0;
for(auto p:qs[id]){
ll cur=t-depth[p.f];
if(cur<0) continue;
//assert(sum[id]!=0);
ans+=cur/sum[id];
cur%=sum[id];
//continue;
int pos=rev[p.s];
//cout<<p.f<<' '<<p.s<<'\n';
//cout<<"pos "<<id<<' '<<pos<<' '<<pre[id].size()<<'\n';
//continue;
if(pre[id][pos]+cur>=sum[id]){
if(pos<=rev[v]){
ans++;
continue;
}
cur-=(sum[id]-pre[id][pos]);
pos=0;
}
int pos2=upper_bound(all(pre[id]),pre[id][pos]+cur)-pre[id].begin()-1;
//cout<<"pos "<<pos<<' '<<pos2<<'\n';
if(pos<=rev[v] and rev[v]<=pos2) ans++;
}
cout<<ans<<'\n';
}
return 0;
}
//maybe its multiset not set
//yeeorz
//laborz
Compilation message
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 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1372 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
