#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<int,int> ii;
lint n, m, L, T;
const int BUFF = 250000;
const int ROOT = 500000;
vector<lint> person;
lint apple[500005];
lint point[500005];
bool vis[500005];
lint getdis(int i){
lint dis = person[i%BUFF] - person[point[i%BUFF]%BUFF];
if(dis < T){
dis += (T/L)*L;
}
while(dis < T) dis += L;
return dis;
}
lint inf = 1e18 + 1e17;
map<lint,lint> infs;
vector<ii> adj[500005];
lint cyclesz[500005];
lint dis[500005];
lint low[500005];
lint high[500005];
lint maxval[500005];
lint total[500005];
lint rep[500005];
vector<lint> stuff[500005];
lint toinf[500005];
lint sumreps[500005];
vector<lint> allreps;
vector<lint> mods[500005];
lint ppcnt = 0;
void dfs(lint u, int p = -1){
low[u] = high[u] = ppcnt++;
for(ii e : adj[u]){
lint v = e.first, w = e.second;
if(v == p) continue;
dis[v] = dis[u] + w;
if(u == ROOT){
rep[v] = v;
allreps.push_back(v);
}
else rep[v] = rep[u];
dfs(v, u);
high[u] = max(high[u], high[v]);
}
}
void dfs2(lint u, int p = -1){
for(ii e : adj[u]){
lint v = e.first;
if(v == p) continue;
dfs2(v, u);
maxval[u] = max(maxval[u], maxval[v]);
total[u] += total[v];
}
}
const int N = (1<<19);
vector<lint> tree[2*N];
inline void addshit(int u, lint t){
t += dis[u];
//show2(u, t);
maxval[u] = max(maxval[u], t);
stuff[rep[u]].push_back(t);
total[u]++;
for(int i = low[u] + N;i > 0;i >>= 1) tree[i].push_back(t);
}
inline void getready(){
for(int i = 0;i < 2*N;i++) sort(all(tree[i]));
}
inline lint get(vector<lint> &v, lint t){
return (lint)(upper_bound(all(v), t) - v.begin());
}
inline lint query(int u, lint t){
lint res = 0;
for(int l = low[u]+N, r = high[u]+N+1;l < r;l >>= 1, r >>= 1){
if(l&1) res += get(tree[l++], t);
if(r&1) res += get(tree[--r], t);
}
return res;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
memset(point, -1, sizeof(point));
cin >> n >> m >> L >> T;
person.resize(n);
for(int i = 0;i < n;i++) cin >> person[i];
for(int i = 0;i < m;i++) cin >> apple[i];
for(int i = 0;i < n;i++){
auto it = upper_bound(all(person), person[i] - (T%L));
if(it == person.begin()) it = upper_bound(all(person), person[i] - (T%L) + L);
it--;
point[i] = it - person.begin();
point[i+BUFF] = point[i]+BUFF;
}
for(int i = 0;i < n;i++){
set<int> cur;
int u = i;
int cycle = -1;
while(true){
if(cur.find(u) != cur.end()) cycle = u;
cur.insert(u);
if(vis[u]) break;
vis[u] = true;
u = point[u];
}
if(cycle == -1) continue;
lint totaldis = 0;
u = cycle;
vector<int> nodes;
while(true){
nodes.push_back(u);
totaldis += getdis(u);
u = point[u];
if(u == cycle) break;
}
for(int x : nodes){
cyclesz[x] = totaldis;
cyclesz[x+BUFF] = totaldis;
}
point[cycle] += BUFF;
point[cycle+BUFF] = ROOT;
}
for(int i = 0;i <= ROOT;i++){
if(point[i] == -1) continue;
if(point[i] == ROOT) adj[ROOT].push_back(ii(i, 0));
else{
lint dis = getdis(i);
adj[point[i]].push_back(ii(i, dis));
}
}
dfs(ROOT);
for(int i = 0;i < m;i++){
auto it = lower_bound(all(person), apple[i]);
if(it == person.begin()) it = person.end();
it--;
int x = it - person.begin();
lint t = apple[i] - person[x];
if(t < 0) t += L;
addshit(x, t);
}
getready();
dfs2(ROOT);
for(lint r : allreps){
//show(r);
for(lint x : stuff[r]){
lint MM = cyclesz[r];
lint I = inf;
I /= MM;
I *= MM;
infs[MM] = I;
lint hm = (I-x)/MM + 1;
sumreps[r] += hm;
//show(hm);
mods[r].push_back(x%MM);
}
sort(all(mods[r]));
}
//show(inf);
int Q; cin >> Q;
while(Q--){
lint u, t; cin >> u >> t; u--;
lint ans = 0;
ans += query(u, t+dis[u]);
if(cyclesz[u+BUFF] != 0){
t += dis[u+BUFF];
lint r = rep[u+BUFF];
ans += sumreps[r];
lint MM = cyclesz[r];
//show2(t, t%MM);
lint fulls = (infs[MM]-(t+1))/MM;
fulls *= sz(stuff[r]);
if(fulls >= 0){
ans -= fulls;
ans -= (sz(stuff[r]) - (upper_bound(all(mods[r]), t%MM) - mods[r].begin()));
}
}
cout << ans << '\n';
}
/*
for(int i = 0;i <= ROOT;i++){
if(point[i] == -1 and i != ROOT) continue;
show3(i, low[i], high[i]);
}
//*/
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
52 ms |
64196 KB |
Output is correct |
| 2 |
Correct |
48 ms |
65572 KB |
Output is correct |
| 3 |
Correct |
50 ms |
65420 KB |
Output is correct |
| 4 |
Incorrect |
49 ms |
65496 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
163 ms |
68324 KB |
Output is correct |
| 2 |
Correct |
394 ms |
105332 KB |
Output is correct |
| 3 |
Correct |
305 ms |
107456 KB |
Output is correct |
| 4 |
Correct |
310 ms |
104660 KB |
Output is correct |
| 5 |
Correct |
486 ms |
125012 KB |
Output is correct |
| 6 |
Correct |
438 ms |
124660 KB |
Output is correct |
| 7 |
Correct |
268 ms |
93152 KB |
Output is correct |
| 8 |
Correct |
256 ms |
93140 KB |
Output is correct |
| 9 |
Correct |
563 ms |
148640 KB |
Output is correct |
| 10 |
Correct |
394 ms |
148224 KB |
Output is correct |
| 11 |
Correct |
860 ms |
147656 KB |
Output is correct |
| 12 |
Correct |
801 ms |
147720 KB |
Output is correct |
| 13 |
Correct |
855 ms |
147720 KB |
Output is correct |
| 14 |
Correct |
696 ms |
147204 KB |
Output is correct |
| 15 |
Correct |
585 ms |
129884 KB |
Output is correct |
| 16 |
Correct |
480 ms |
115468 KB |
Output is correct |
| 17 |
Correct |
432 ms |
114904 KB |
Output is correct |
| 18 |
Correct |
261 ms |
79816 KB |
Output is correct |
| 19 |
Correct |
291 ms |
79668 KB |
Output is correct |
| 20 |
Correct |
353 ms |
103844 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
52 ms |
64196 KB |
Output is correct |
| 2 |
Correct |
48 ms |
65572 KB |
Output is correct |
| 3 |
Correct |
50 ms |
65420 KB |
Output is correct |
| 4 |
Incorrect |
49 ms |
65496 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
