#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int bar = (1<<16);
const int INF= (1<<29)-1;
struct Node{
pii min;
pii max;
static Node e(){
return Node{pii(INF, -1), pii(-INF, -1)};
}
};
struct Tree{
Node tree[2*bar];
Tree(vector<Node>& v){
build(v, 0, v.size()-1, 1);
}
static Node merge(Node a, Node b){
Node res;
if(a.min<=b.min){
res.min = a.min;
}
else{
res.min = b.min;
}
if(a.max>=b.max){
res.max = a.max;
}
else{
res.max= b.max;
}
return res;
}
void build(vector<Node>& v, int lt, int rt, int t){
if(lt==rt){
tree[t] = v[lt];
}
else{
int mid = (lt+rt)/2;
build(v, lt, mid, t*2);
build(v, mid+1, rt, t*2+1);
tree[t] = merge(tree[t*2], tree[t*2+1]);
}
}
Node range_q(int l, int r, int lt, int rt, int t){
if(rt<l || r< lt){
return Node::e();
}
else if(l<= lt && rt <= r){
return tree[t];
}
else{
int mid = (rt+lt)/2;
return merge(range_q(l, r, lt, mid, t*2),range_q(l, r, mid+1, rt, t*2+1));
}
}
};
struct Line{
int l, r;
int dest;
bool right;
int pre_pos, post_pos;
Node transition;
};
vector<Line> lines;
vector<Node> pre;
vector<Node> post;
vector<Node> im;
int main(){
int n, k, m;
cin>>n>>k>>m;
for(int i = 0; i<m; i++){
int a, b;
cin>>a>>b;
a--;
b--;
Line l;
if(a<b){
l.l = a;
l.r = min(a+k-1, b);
l.dest =b;
l.right = true;
pre.push_back(Node{pii(l.r, i), pii(b, i)});
post.push_back(Node{pii(l.r, i), pii(b, i)});
}
else{
l.l = max(a-k+1, b);
l.r = a;
l.dest =b;
l.right = false;
pre.push_back(Node{pii(b, i), pii(l.l, i)});
post.push_back(Node{pii(b, i), pii(l.l, i)});
}
lines.push_back(l);
}
for(int i = 0; i<n; i++){
Line l;
l.l = i;
l.r= i;
l.dest=i;
l.transition = Node{pii(i, i+m), pii(i, i+m)};
lines.push_back(l);
l.right = true;
pre.push_back(l.transition);
post.push_back(l.transition);
}
m+=n;
auto pre_cmp = [&](Node a, Node b){
return lines[a.min.second].l<lines[b.min.second].l;
};
auto post_cmp = [&](Node a, Node b){
return lines[a.min.second].r<lines[b.min.second].r;
};
sort(pre.begin(), pre.end(), pre_cmp);
sort(post.begin(), post.end(), post_cmp);
//cout<<"done "<<endl;
im.resize(n);
set<pii> ms;
int pre_id= 0, post_id = 0;
for(int i = 0; i<n; i++){
while(post_id<post.size() && lines[post[post_id].min.second].r ==i-1){
ms.erase(pii(lines[post[post_id].min.second].dest, post[post_id].min.second));
post_id++;
}
while(pre_id<pre.size() && lines[pre[pre_id].min.second].l ==i){
ms.insert(pii(lines[pre[pre_id].min.second].dest, pre[pre_id].min.second));
pre_id++;
}
im[i]= Node{pii(i, i+m-n), pii(i, i+m-n)};
if(ms.size()>0){
//cout<<(*ms.begin()).first<<" "<<(*ms.begin()).second<<" "<<(--ms.end())->first<<" "<<(--ms.end())->second<<endl;
im[i] = Tree::merge(im[i], Node{*ms.begin(), *(--ms.end())});
}
//cout<<"im "<<i<<" "<<im[i].min.first<<" "<<im[i].max.first<<endl;
//cout<<"im "<<i<<" "<<im[i].min.second<<" "<<im[i].max.second<<endl;
}
//cout<<"hello"<<endl;
for(int i = 0; i<m; i++){
lines[pre[i].min.second].pre_pos = i;
lines[post[i].min.second].post_pos = i;
}
vector<int> first_oc_pre(n);
for(int i =m-1; i>=0; i--){
first_oc_pre[lines[pre[i].min.second].l] = i;
}
vector<int> last_oc_post(n);
for(int i =0; i<m; i++){
last_oc_post[lines[post[i].min.second].r] = i;
}
Tree pre_tree = Tree(pre);
Tree post_tree = Tree(post);
for(int i = 0; i<m; i++){
//cout<<lines[i].l<<" "<<lines[i].r<<" "<<lines[i].dest<<endl;
if(lines[i].right){
pii inter = pii(first_oc_pre[lines[i].l], lines[i].pre_pos);
for(int step = (1<<20); step>=1; step/=2){
if(inter.second + step<m){
auto next = inter.second +step;
if(lines[pre[next].min.second].l<=lines[i].dest){
inter.second += step;
}
}
}
//cout<<inter.first<<" "<<inter.second<<endl;
lines[i].transition = pre_tree.range_q(inter.first, inter.second, 0, m-1, 1);
for(int j= inter.first; j<=inter.second; j++){
//cout<<lines[pre[j].min.second].l<<" "<<lines[pre[j].min.second].r<<" | ";
}
//cout<<endl;
}
else{
pii inter = pii(lines[i].post_pos, last_oc_post[lines[i].r]);
for(int step = (1<<20); step>=1; step/=2){
if(inter.first -step>=0){
auto next = inter.first -step;
if(lines[post[next].min.second].r>= lines[i].dest){
inter.first -= step;
}
}
}
//cout<<inter.first<<" "<<inter.second<<endl;
lines[i].transition = post_tree.range_q(inter.first, inter.second, 0, m-1, 1);
}
//cout<<"transition "<<lines[i].transition.min.first<<" "<<lines[i].transition.max.first<<endl;
//cout<<"transition "<<lines[i].transition.min.second<<" "<<lines[i].transition.max.second<<endl;
}
vector<vector<Node>> tr(18, vector<Node>(m));
for(int i = 0; i<m; i++){
tr[0][i] = lines[i].transition;
//tr[0][i] = pre[lines[i].pre_pos];
}
for(int step = 1; step<18; step++){
for(int i = 0; i<m; i++){
int a = tr[step-1][i].min.second;
int b = tr[step-1][i].max.second;
tr[step][i] = Tree::merge(tr[step-1][a], tr[step-1][b]);
}
}
//cout<<"displaying depth 0"<<endl;
for(int i = 0; i<m; i++){
//cout<<lines[i].transition.min.second<<" "<<lines[i].transition.max.second<<endl;
//cout<<lines[i].l<<" "<<lines[i].r<<" "<<lines[i].dest<<" "<<tr[0][i].min.first<<" "<<tr[0][i].max.first<<endl;
}
int q;
cin>>q;
//cout<<"q: "<<q<<endl;
for(int i = 0; i<q; i++){
int a, b;
cin>>a>>b;
a--;
b--;
int res= 1;
if(a==b){
cout<<0<<endl;
continue;
}
Node cur = im[a];
if(b>=cur.min.first && b<= cur.max.first){
cout<<res<<endl;
continue;
}
if(cur.min.second ==-1&&cur.max.second ==-1){
cout<<-1<<endl;
continue;
}
//cout<<"anwsering"<<endl;
//cout<<cur.min.first<<" "<<cur.max.first<<endl;
//cout<<cur.min.second<<" "<<cur.max.second<<endl;
for(int step = 17; step>=0; step--){
int cost = (1<<step);
Node next;
Node min_d =tr[step][cur.min.second];
//cout<<"min_d "<<cur.min.second<<" "<<min_d.min.first<<" "<<min_d.max.first<<endl;
Node max_d = tr[step][cur.max.second];
//cout<<"max_d "<<cur.max.second<<" "<<max_d.min.first<<" "<<max_d.max.first<<endl;
next = Tree::merge(min_d, max_d);
if(b<next.min.first || b> next.max.first){
cur = next;
res += cost;
//cout<<"taking"<<endl;
}
//cout<<cur.min.first<<" "<<cur.max.first<<endl;
//cout<<cur.min.second<<" "<<cur.max.second<<endl;
}
Node next;
Node min_d =tr[0][cur.min.second];
Node max_d = tr[0][cur.max.second];
next = Tree::merge(min_d, max_d);
if(b<next.min.first || b> next.max.first){
cout<<-1<<endl;
continue;
}
else{
//cout<<"final : "<<next.min.first<<" "<<next.max.first<<endl;
cout<<res+1<<endl;
continue;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
136 ms |
45452 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
178 ms |
46824 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
