#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define pii pair<ll, pi>
#define f first
#define s second
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pi, null_type,less<pi>, rb_tree_tag,
tree_order_statistics_node_update> oset;
struct omset{
oset s;
map<int, int> mp;
void clr(){
s.clear();
mp.clear();
}
void add(int x){
s.insert({x, mp[x]++});
}
int qry(int x){
return s.order_of_key({x + 1, -1});
}
int qry(int a, int b){
return qry(b) - qry(a - 1);
}
};
const int mxn = 200001;
int n, m, k, w, q;
int a[mxn], b[mxn];
ll p[mxn], rt[mxn], l[mxn], r[mxn], d[mxn];
bool vis[mxn], vis2[mxn];
vector<pii> qry;
vector<pii> qv[mxn];
vector<ll> g[mxn], v[mxn];
omset tre;
ll ans[mxn];
int s, t;
int dfs(int c){
l[c] = r[c] = t++;
for(int i : g[c]){
if(~rt[i]) continue;
d[i] = d[c] + (k + a[i] - a[c]) % k;
rt[i] = rt[c];
r[c] = dfs(i);
}
return r[c];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k >> w;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < m; i++) cin >> b[i];
//init graph
for(int i = 0; i < n; i++){
rt[i] = -1;
p[i] = (n + upper_bound(a, a + n, (k + a[i] - w) % k) - a - 1) % n;
g[p[i]].push_back(i);
}
for(int i = 0; i < n; i++){
if(!vis[i]){
int j;
for(j = i; !vis[p[j]]; j = p[j]) vis[j] = vis2[j] = 1;
if(vis2[p[j]]){
for(int l = p[j]; l != j; l = p[l]){
v[s].push_back(l);
rt[l] = l;
}
v[s].push_back(j);
rt[j] = j;
s++;
}
for(int l = i; l != j; l = p[l]) vis2[l] = 0;
vis2[j] = 0;
}
}
for(int i = 0; i < s; i++)
for(int j : v[i]){
dfs(j);
}
//end init graph
cin >> q;
for(int i = 0; i < q; i++){
ll x, y;
cin >> x >> y;
x--;
pii z = {d[x] + y, {i, x}};
//if(rt[x] == x) qv[x].push_back(z);
qry.push_back(z);
}
for(int i = 0; i < m; i++){
int x = (n + upper_bound(a, a + n, b[i]) - a - 1) % n;
pii z = {d[x] + (k + b[i] - a[x]) % k, {-1, x}};
//qv[rt[x]].push_back(z);
qry.push_back(z);
}
sort(qry.begin(), qry.end());
for(pii i : qry){
if(!~i.s.f) tre.add(l[i.s.s]);
else ans[i.s.f] = tre.qry(l[i.s.s], r[i.s.s]);
}
return 0;
for(int i = 0; i < s; i++){
qry.clear();
tre.clr();
for(int j : v[i])
for(pii l : qv[j]){
pii z = l;
z.f += (k + a[j] - v[i][0]) % k;
qry.push_back(z);
}
sort(qry.begin(), qry.end());
ll dt = 0, len = (k + a[p[v[i][0]]] - a[v[i][0]]) % k;
for(pii j : qry){
if(!~j.s.f){
dt -= j.f / len;
tre.add(j.f % len);
}else{
ans[j.s.f] += dt + tre.qry(len) * (j.f / k) + tre.qry(j.f % len);
}
}
}
for(int i = 0; i < q; i++) cout << ans[i] << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
19584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
