#include <bits/stdc++.h>
using namespace std;
int N,Q;
int lst[200100];
vector<int> pos[200100];
int l[25][200100];
int r[25][200100];
map<pair<int,int>,int> mep;
int direc[200100][2];
struct node{
int s, e, m;
int v;
node *l, *r;
node(int S, int E){
s = S;
e = E;
m = (s + e)/2;
if(s != e){
l = new node(s,m);
r = new node(m + 1, e);
v = max(l -> v, r -> v);
}
else{
v = lst[s];
}
}
int query(int S, int E){
if(S <= s && e <= E) return v;
int V = 0;
if(S <= m) V = max(V, l -> query(S,E));
if(m < E) V = max(V, r -> query(S,E)) ;
return V;
}
}*root;
int main(){
int K;
scanf(" %d",&N);
scanf(" %d",&K);
scanf(" %d",&Q);
for(int i = 1; i <= N; i++){
scanf(" %d",&lst[i]);
if(i != 1 && i != N) pos[lst[i]].push_back(i);
}
vector<int> steck = {1};
direc[1][0] = -1;
for(int i = 2; i <= N; i++){
while(lst[steck.back()] < lst[i]) steck.pop_back();
direc[i][0] = steck.back();
steck.push_back(i);
}
direc[N][1] = -1;
steck = {N};
for(int i = N - 1; i >= 1; i--){
while(lst[steck.back()] < lst[i]) steck.pop_back();
direc[i][1] = steck.back();
steck.push_back(i);
}
root = new node(1,N);
for(int i = 1; i <= N; i++){
l[0][i] = max(1,direc[i][0]);
r[0][i] = min(N,direc[i][1]);
}
r[0][N] = N;
for(int j = 1; j < 25; j++){
for(int i = 1; i <= N; i++){
l[j][i] = min(l[j - 1][l[j - 1][i]], l[j - 1][r[j - 1][i]]);
r[j][i] = max(r[j - 1][l[j - 1][i]], r[j - 1][r[j - 1][i]]);
}
}
for(int i = 0; i < Q; i++){
int A, B;
scanf(" %d",&A);
scanf(" %d",&B);
int num = 0;
int l1, r1;
l1 = A;
r1 = A;
for(int j = 24; j >= 0; j--){
if(max(r[j][l1], r[j][r1]) < B || B < min(l[j][l1], l[j][r1])){
int temp = min(l[j][l1], l[j][r1]);
r1 = max(r[j][l1], r[j][r1]);
l1 = temp;
num += (1<<j);
}
}
int l2,r2;
l2 = B;
r2 = B;
for(int j = 24; j >= 0; j--){
if(max(r[j][l2], r[j][r2]) < l1 || r1 < min(l[j][l2], l[j][r2])){
int temp = min(l[j][l2], l[j][r2]);
r2 = max(r[j][l2], r[j][r2]);
l2 = temp;
num += (1<<j);
}
}
printf("%d\n",num + 1 - 1);
}
}
Compilation message (stderr)
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf(" %d",&N);
| ~~~~~^~~~~~~~~~
railway_trip.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf(" %d",&K);
| ~~~~~^~~~~~~~~~
railway_trip.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf(" %d",&Q);
| ~~~~~^~~~~~~~~~
railway_trip.cpp:55:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf(" %d",&lst[i]);
| ~~~~~^~~~~~~~~~~~~~~
railway_trip.cpp:101:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf(" %d",&A);
| ~~~~~^~~~~~~~~~
railway_trip.cpp:102:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | scanf(" %d",&B);
| ~~~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |