#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
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
const int mxn = 200001;
struct BIT{
int bit[mxn];
BIT(){
clr();
}
void clr(){
memset(bit, 0, sizeof(bit));
}
void add(int x, int v){
for(x++; x < mxn; x += x & -x) bit[x] += v;
}
int qry(int x){
int ret = 0;
for(x++; x; x -= x & -x) ret += bit[x];
return ret;
}
int qry(int a, int b){
return qry(b) - qry(a - 1);
}
};
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];
BIT bit;
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) bit.add(l[i.s.s], 1);
else ans[i.s.f] = bit.qry(l[i.s.s], r[i.s.s]);
}
for(int i = 0; i < s; i++){
qry.clear();
bit.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;
bit.add(j.f % len, 1);
}else{
ans[j.s.f] += dt + bit.qry(len) * (j.f / k) + bit.qry(j.f % len);
}
}
}
for(int i = 0; i < q; i++) cout << ans[i] << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
29 ms |
31232 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
143 ms |
51520 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
29 ms |
31232 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
