#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=2e5+5, MK=18;
int N,K,M,Q;
struct segtree {
pair<int,int> t[4 * MX];
void set(int v, int l, int r, int pos, pair<int,int> val) {
if(l > pos || r < pos) return;
if(l == r) {
t[v] = val;
return;
}
int mid = (l + r) >> 1;
set(v * 2 + 0, l, mid + 0, pos, val);
set(v * 2 + 1, mid + 1, r, pos, val);
t[v] = max(t[v * 2 + 0], t[v * 2 + 1]);
}
void update(int v, int l, int r, int pos, pair<int,int> val) {
if(l > pos || r < pos) return;
if(l == r) {
t[v] = max(t[v],val);
return;
}
int mid = (l + r) >> 1;
update(v * 2 + 0, l, mid + 0, pos, val);
update(v * 2 + 1, mid + 1, r, pos, val);
t[v] = max(t[v * 2 + 0], t[v * 2 + 1]);
}
pair<int,int> query(int v, int l, int r, int ql, int qr) {
if(ql > r || qr < l) return make_pair(0,0);
if(ql <= l && qr >= r) return t[v];
int mid = (l + r) >> 1;
return max(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
}
void reset() {
for(int i=0;i<4*MX;i++)
t[i]=make_pair(0,0);
}
} st;
int L[MX], R[MX], dep[MX], S[MX], T[MX], nxt[MX];
vector<int> adj[MX];
int up[MX][MK];
bool root[MX];
void dfs(int v) {
for(int k=1;k<MK;k++) {
up[v][k]=up[up[v][k-1]][k-1];
}
for(auto u:adj[v]) {
dep[u]=dep[v]+1;
up[u][0]=v;
dfs(u);
}
}
set<pair<int,int>> pends[MX];
int find(int v, int r) {
for(int k=MK-1;k>=0;k--) {
if(up[v][k]!=0 && R[up[v][k]]<r) {
v=up[v][k];
}
}
return up[v][0];
}
int ans[MX];
void work() {
for(int i=0;i<MX;i++) {
dep[i]=0;
nxt[i]=0;
pends[i].clear();
pends[i].insert(make_pair(0,0));
adj[i].clear();
root[i]=1;
for(int j=0;j<MK;j++) {
up[i][j]=0;
}
}
st.reset();
vector<array<int,3>> v;
for(int i=1;i<=M;i++) {
if(L[i]>R[i]) continue;
v.push_back({L[i],0,i});
v.push_back({min(L[i]+K-1,R[i]-1),1,i});
v.push_back({R[i],2,i});
}
sort(v.begin(),v.end());
for(auto [p,t,id]:v) {
if(t==0) {
st.update(1,1,N,p,make_pair(R[id],id));
} else if(t==1) {
} else {
int nxt=st.query(1,1,N,L[id],R[id]).second;
if(nxt!=0 && nxt!=id) {
root[id]=0;
adj[nxt].push_back(id);
}
}
}
for(int i=1;i<=M;i++) {
if(root[i] && L[i]<R[i]) dfs(i);
}
st.reset();
v.clear();
for(int i=1;i<=N;i++) {
v.push_back({i,1,-1});
}
for(int i=1;i<=M;i++) {
v.push_back({L[i],0,i});
v.push_back({min(L[i]+K-1,R[i]-1),2,i});
}
sort(v.begin(),v.end());
multiset<int> mx,mn;
for(auto [p,t,id]:v) {
if(t==0) {
pends[p].insert(make_pair(R[id],id));
st.set(1,1,N,p,*pends[p].rbegin());
} else if(t==1) { // query
nxt[p]=st.query(1,1,N,1,p).second;
} else {
pends[L[id]].erase(make_pair(R[id],id));
st.set(1,1,N,L[id],*pends[L[id]].rbegin());
}
}
for(int i=1;i<=Q;i++) {
if(S[i]>T[i]) continue;
int s=S[i], t=T[i];
if(nxt[s]==0) {
ans[i]=-1;
continue;
}
if(R[nxt[s]]>=t) {
ans[i]=1;
continue;
}
int T=find(nxt[s],t);
if(T==0) {
ans[i]=-1;
continue;
}
ans[i]=dep[nxt[s]]-dep[T]+1;
}
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N>>K>>M;
for(int i=1;i<=M;i++) {
cin>>L[i]>>R[i];
}
cin>>Q;
for(int i=1;i<=Q;i++) {
cin>>S[i]>>T[i];
}
work();
for(int i=1;i<=M;i++) {
L[i]=N-L[i]+1;
R[i]=N-R[i]+1;
}
for(int i=1;i<=Q;i++) {
S[i]=N-S[i]+1;
T[i]=N-T[i]+1;
}
work();
for(int i=1;i<=Q;i++) {
cout<<ans[i]<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
49748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
49748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
223 ms |
63304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
225 ms |
60132 KB |
Output is correct |
| 2 |
Correct |
637 ms |
70324 KB |
Output is correct |
| 3 |
Correct |
277 ms |
69060 KB |
Output is correct |
| 4 |
Correct |
610 ms |
71356 KB |
Output is correct |
| 5 |
Correct |
679 ms |
69836 KB |
Output is correct |
| 6 |
Correct |
672 ms |
69908 KB |
Output is correct |
| 7 |
Correct |
526 ms |
70840 KB |
Output is correct |
| 8 |
Correct |
530 ms |
70756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
565 ms |
68968 KB |
Output is correct |
| 2 |
Correct |
274 ms |
70808 KB |
Output is correct |
| 3 |
Correct |
173 ms |
62220 KB |
Output is correct |
| 4 |
Correct |
117 ms |
58760 KB |
Output is correct |
| 5 |
Correct |
78 ms |
53880 KB |
Output is correct |
| 6 |
Correct |
73 ms |
53048 KB |
Output is correct |
| 7 |
Correct |
302 ms |
66272 KB |
Output is correct |
| 8 |
Correct |
24 ms |
49756 KB |
Output is correct |
| 9 |
Correct |
28 ms |
50008 KB |
Output is correct |
| 10 |
Correct |
555 ms |
68224 KB |
Output is correct |
| 11 |
Correct |
586 ms |
69188 KB |
Output is correct |
| 12 |
Correct |
564 ms |
69232 KB |
Output is correct |
| 13 |
Correct |
628 ms |
68828 KB |
Output is correct |
| 14 |
Correct |
27 ms |
49864 KB |
Output is correct |
| 15 |
Correct |
28 ms |
50012 KB |
Output is correct |
| 16 |
Correct |
524 ms |
69760 KB |
Output is correct |
| 17 |
Correct |
489 ms |
70608 KB |
Output is correct |
| 18 |
Correct |
520 ms |
70192 KB |
Output is correct |
| 19 |
Correct |
496 ms |
70076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
49748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
