//#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;
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>> qs[mxn];
vector<vector<ll>> pre;
int n,m,l,c;
int timer=1;
void dfs(int p,int v){
st[v]=timer;
/*if(v<n) */timer++;
if(v>=n){
sta.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);
}
en[v]=timer;
}
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;
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++){
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]];
}
if(d[i]==0){
d[i]=(C+l-1)/l*l;
}
else{
d[i]+=1ll*(C/l)*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++){
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]]);
}
for(int i=0;i<(int)curcycle.size();i++){
int prv=(i-1+(int)curcycle.size())%(int)curcycle.size();
dis.push_back(dis.back()+d[curcycle[prv]]);
}
pre.push_back(dis);
}
for(int i=0;i<(int)cycle.size();i++){
int cnt=0;
for(auto v:cycle[i]){
sta.clear();
dfs(v,v);
qs[i].insert(qs[i].end(),all(sta));
sum[i]+=d[v];
rev[v]=cnt++;
}
}
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]){
//res[i]=dfs_ans(v,v,t);
qys.push_back({t+depth[v],{i,v}});
continue;
}
int id=belong[v];
ll ans=0;
for(auto p:qs[id]){
ll cur=t-depth[p.f];
if(cur<0) continue;
ans+=cur/sum[id];
cur%=sum[id];
int pos=rev[p.s];
int pos2=upper_bound(all(pre[id]),pre[id][pos]+cur)-pre[id].begin()-1;
if((pos<=rev[v] and rev[v]<=pos2) or (pos<=rev[v]+(int)cycle[id].size() and rev[v]+(int)cycle[id].size()<=pos2)) ans++;
}
res[i]=ans;
}
for(int i=n;i<n+m;i++){
if(depth[i]==0) continue;
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);
}
}
for(int i=0;i<q;i++){
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 '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 |
7 ms |
32860 KB |
Output is correct |
| 2 |
Correct |
9 ms |
33744 KB |
Output is correct |
| 3 |
Correct |
88 ms |
33876 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
33588 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5053 ms |
33112 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
32860 KB |
Output is correct |
| 2 |
Correct |
9 ms |
33744 KB |
Output is correct |
| 3 |
Correct |
88 ms |
33876 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
33588 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
