#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<pair<long long,long long>,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> orderedset;
#define int long long
const int INF = 1e18;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,l,c;
cin >> n >> m >> l >> c;
vector<int> employee(2e5+10);
vector<int> apple(m);
vector<pair<int,int>> adj(2e5+10);
vector<vector<int>> revadj(2e5+10);
for(int i=1;i<=n;i++)cin>>employee[i];
for(int&i:apple)cin>>i;
for(int i=1;i<=n;i++){
int modded = c%l;
int iter = 0;
for(int jump=131072;jump;jump/=2){
if(iter+jump>n)continue;
if((l+employee[i]-employee[(n-iter-jump+i)%n +1])%l < modded)iter+=jump;
}
iter++;
if(iter==n+1){
adj[i] = {i,(c/l)*l + l};
continue;
}
adj[i] = {(n-iter+i)%n +1,(c/l)*l + (l+employee[i]-employee[(n-iter+i)%n +1])%l};
revadj[adj[i].first].emplace_back(i);
}
vector<int> depth(2e5+10);
vector<bool> visited(2e5+10);
vector<int> heads;
function<void (int)> front_dfs = [&](int x){
if(visited[x])return;
visited[x]=true;
front_dfs(adj[x].first);
if(depth[adj[x].first]==0)heads.emplace_back(x);
depth[x] = depth[adj[x].first]+adj[x].second;
};
for(int i=1;i<=n;i++)if(!visited[i])front_dfs(i);
vector<vector<int>> apples(2e5+10);
vector<vector<pair<int,int>>> queries(2e5+10);
for(int&i:apple){
int start = -1;
if(i<employee[1])start = n;
else {
start = upper_bound(employee.begin()+1,employee.end(),i)-employee.begin()-1;
}
apples[start].emplace_back((l+i-employee[start])%l);
}
int q;
cin >> q;
vector<int> ans(q+1);
for(int i=1;i<=q;i++){
int v,t;
cin >> v >> t;
queries[v].emplace_back(t,i);
}
visited = vector<bool>(2e5+10);
int uid = 0;
function<orderedset(int)> calc_linear_dfs = [&](int x){
orderedset curr;
if(visited[x])return curr;
visited[x] = true;
for(int&i:revadj[x]){
auto t = calc_linear_dfs(i);
if(curr.size()<t.size())swap(curr,t);
for(auto j:t)curr.insert(j);
}
for(int&i:apples[x])curr.insert({i+depth[x],++uid});
for(auto[t,idx]:queries[x]){
ans[idx] = curr.order_of_key({t+depth[x],INF});
}
return curr;
};
for(int&i:heads){
auto t = calc_linear_dfs(i);
orderedset curr;
int cycle_len = depth[adj[i].first];
int offset = 0;
for(auto [x,y]:t)curr.insert({(x-adj[i].second)%cycle_len,y});
for(auto [x,y]:t)offset-=(x-adj[i].second)/cycle_len;
function<void(int,int)> calc = [&](int x,int len){
for(auto[t,idx]:queries[x]){
t-=len;
if(t<0)continue;
ans[idx]+=curr.size()*(t/cycle_len);
t%=cycle_len;
ans[idx]+=curr.order_of_key({t,INF});
ans[idx]+=offset;
}
if(x==i)return;
calc(adj[x].first,len+adj[x].second);
};
calc(adj[i].first,adj[i].second);
}
for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
20828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
29372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
20828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
