#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];
struct query{
lint u, t, id, ans;
};
vector<query> queries;
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 shitquery(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;
}
vector<lint> disshit;
int getshit1(lint i){
int pos = lower_bound(all(disshit), i) - disshit.begin() + 1;
//show2(i, disshit[pos-1]);
assert(i == disshit[pos-1]);
return pos;
}
vector<lint> history;
lint ft[1400005];
void unshitupdate(int i){
i = getshit1(i);
if(i == 0) return;
history.push_back(i);
for(;i <= 1400001;i += i&(-i)){
ft[i]++;
}
}
lint unshitquery(int i){
i = getshit1(i);
int res = 0;
for(;i > 0;i -= i&(-i)) res += ft[i];
return res;
}
void undoall(){
while(not history.empty()){
int i = history.back();
history.pop_back();
if(i == 0) continue;
for(;i <= 1400001;i += i&(-i)){
ft[i] = 0;
}
}
}
int main(){
//freopen("i.txt","r",stdin);
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;
disshit.push_back(x % MM);
lint hm = (I-x)/MM + 1;
sumreps[r] += hm;
//show(hm);
mods[r].push_back(x%MM);
}
sort(all(mods[r]));
sort(all(stuff[r]));
}
//show(inf);
int Q; cin >> Q;
for(int q = 0;q < Q;q++){
lint u, t; cin >> u >> t;
u--;
queries.push_back({u,t,q,0});
if(cyclesz[u+BUFF] != 0){
lint r = rep[u+BUFF];
lint MM = cyclesz[r];
disshit.push_back((t+dis[u+BUFF])%MM);
}
}
sort(all(disshit));
disshit.erase(unique(all(disshit)), disshit.end());
sort(all(queries), [&](query a, query b){
if(rep[a.u] == rep[b.u]) return a.t < b.t;
else return rep[a.u] < rep[b.u];
});
lint prevrep = -1;
lint sumofshit = 0;
lint shitcnt = 0;
int ptr = 0;
for(query &q : queries){
lint u = q.u, t = q.t;
lint ans = 0;
if(rep[u] != prevrep){
prevrep = rep[u];
undoall();
sumofshit = 0;
shitcnt = 0;
ptr = 0;
}
ans += shitquery(u, t+dis[u]);
if(cyclesz[u+BUFF] != 0){
t += dis[u+BUFF];
lint r = rep[u+BUFF];
lint MM = cyclesz[r];
while(ptr < sz(stuff[r])){
if(stuff[r][ptr] > t) break;
else{
sumofshit += (infs[MM]-stuff[r][ptr])/MM + 1;
//shitmods.push_back(stuff[r][ptr] % MM); ///change this
unshitupdate(stuff[r][ptr] % MM);
ptr++;
shitcnt++;
}
//sort(all(shitmods));
}
ans += sumofshit;
lint fulls = (infs[MM]-(t+1))/MM;
fulls *= shitcnt;
if(fulls >= 0){
ans -= fulls;
ans -= (shitcnt - unshitquery(t%MM)); ///change this
}
}
q.ans = ans;
}
sort(all(queries), [&](query a, query b){ return a.id < b.id; });
for(query q : queries) cout << q.ans << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
64460 KB |
Output is correct |
| 2 |
Correct |
47 ms |
65860 KB |
Output is correct |
| 3 |
Correct |
46 ms |
65740 KB |
Output is correct |
| 4 |
Runtime error |
107 ms |
133068 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
237 ms |
79216 KB |
Output is correct |
| 2 |
Runtime error |
375 ms |
212816 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
64460 KB |
Output is correct |
| 2 |
Correct |
47 ms |
65860 KB |
Output is correct |
| 3 |
Correct |
46 ms |
65740 KB |
Output is correct |
| 4 |
Runtime error |
107 ms |
133068 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
