/*
.... ...::--::::::..
.-+*#%%%%%%%*++=#%@@%%%%@@@%%%%%#+-:
-*%%%%%%@%%%%@@@%%@@@@@@@@@@%%@@@%%%%##%#*-
:*@%%@@@@@@%%@@@@@@@@@@@@@@@@@@@@%@@@@@%%%%%%%#-
-#@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@%%@@@@@%%%%%%%#:
.*@%%@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@%@@@%%@@@@%%@%%%%@+
-#%@%@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@%%@@@@@@@@%@@@%%%@+
-%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@%%@@@@@@@@@@@@%%%@+
.%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%@@@@@@@%@@@@@@@@+
.%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%@@@%@@%@@@@%@@@@=
#@%@@@@@@@@@@@@@@@@@%%@@%%%%%%%%%%%%@%@%%%%@%%%%@%@@%%%@%%%@@%%.
=@%@@@@@@@@@@@@@@@@@%%%%%%%%#%%%%%%%%%%%%%%%%%%@%%@@@@@%@%%%%@@%%.
.@%%@%@@@@@@@@@@@%@%%%%#%%%##+**%%%%#%%%%###%%%%%%%@%%@@%%%%%%@@@@.
-@%%%@@@@@@@@@@%%%%%%%#*#%#*++=++****++++++**#%###%@@@%@%%@%%%%@@@-
-@%%@@@@@@@@@@%%#####%*+++====-=====------===+++=++#%@@@%%@%%%%%%%=
.@%@%%@@@@@@@%##**+*+++==-----------------------===+*%%%@%%%%%%%%#.
*@@@%@%@@@%#***+***++==--------------------===++===+#%%@@%%%%%%+-
-%@@%@%@@%#****###%%%%#*+===---------==+**####**+++++#%%%%%%%%%:
#@@%@%@%#*+++++++++++***+++===----===+++++========+++#%@%%%%%-
-@@%@@@#+=+++++++=======++===-----=====++============+#@%%%@*
.@@@@%@*===++**#*#@#%#++====-------===++#@%@**#*++==--+@%%%#:
.##%@%%*====++**+=*#*-=++--=---------=+==+*+======----=@%*==-
++*#%%+==============-----=---:----------------------=%%==+=
.+=+*%+==-----------:--------:::-----:::-----::::-----%#--=.
-=+*%*===--------::::-------:::-::-:::::::::::::----=%+=-:
==+%#===------::::::--==---::::----::::::::::::----+#==:
:++*#===--------:::---=----::::::--::::::::::::----++=-
-=+#+===-------:--:-=-====---==---:::::::::::-----+--
==++=====-------:--=+***+++++**+-:::::::::------==-.
.==+====------------=++=========-::::::--------==::
=====----------=========------:::::-------==
+======----=======----------------------==-
:+==========++++**+=++===+++++=--------==+.
=+==========***++=========++=--------===:
=++=========++++==----=====-----======-
-+++==========+++++++++==-----=======+:
:*+++++=============--------==========:
.*+**++++=======-----------======+++==:
+++*****++++=================++++====:
:++++++*****++++++++++++==++++++======-
=%=+++++++******************+++====--===*-
-%%=======+++++++++++++++++=======-----=-+#-
-*%@++======++++++++==============------==+%*:
=+*#%*+=======+++++++++==-========------===*#*+-
.:****#%#*+========++++++++++=======------===+##++==-:.
.-=+**#*#***##*++========================---======*#**++*++*++=-.
.-=+##***#####***###*++==============-=--=====--======+#**+++++++*+++**+=:
.-=*#####*##########*####*++==============--=============+#*#**++++++*****+*+**+-.
.-+*#####################*#####+++==========================+***#****+++*+***********++=
+###################*#############*++========================*#*******++++++*******+******
####################*#############%**+===-===========--=====*#**#**+++++++++**************
###########################*##%@%%@%#*+=-----====--------=+*##*#@@@%#*++++++**************
########################**#%@@%%%%%%#%%#*=--------------+***#*#@%@@%%@%#++++***###********
######################**#%%%%%%%%%%%%%%%%%#+--::::---=+#**###%@%%%%%%%%%@***#####***+*****
^^pavement for goodluck
*/
//Beichen is a classic problem in China
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
#define int long long
#define test cout<<"test\n"<<flush;
#define endl "\n"
#define exit return 0
#define iloop(n) for(int i=0;i<n;i++)
#define jloop(n) for(int j=0;j<n;j++)
#define kloop(n) for(int k=0;k<n;k++)
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define pii pair<int,int>
#define hashmap unordered_map
#define coutpair(p) cout<<p.first<<" "<<p.second<<endl;
#define couttrip(a,b,c) cout<<a<<" "<<b<<" "<<c<<" ";
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
const int NMAX=100005;
int c[NMAX];
int d[NMAX];
vector<int> v[NMAX];
int mem[NMAX][20];
int depth[NMAX];
void dfs(int cur,int par,int d){
depth[cur]=d;
mem[cur][0]=par;
iloop(18){
int h=mem[cur][i];
if(h==-1){
continue;
}
mem[cur][i+1]=mem[h][i];
}
for(auto it:v[cur]){
if(it!=par){
dfs(it,cur,d+c[it]);
}
}
}
int query(int cur,int k){
if(cur==-1){
return -1;
}
iloop(19){
if(((1<<i)&k)==0){
continue;
}
cur=mem[cur][i];
if(cur==-1){
return -1;
}
}
return cur;
}
int range(int a,int b){
if(b==-1 or mem[b][0]==-1){
return depth[a];
}
return depth[a]-depth[mem[b][0]];
}
signed main(){
fastio
int n,q;
cin>>n>>q;
iloop(n){
cin>>d[i]>>c[i];
}
stack<int> s;
iloop(n){
if(s.empty()){
s.push(i);
continue;
}
while(!s.empty() and d[s.top()]<d[i]){
v[i].pb(s.top());
v[s.top()].pb(i);
s.pop();
}
s.push(i);
}
while(!s.empty()){
v[n].pb(s.top());
v[s.top()].pb(n);
s.pop();
}
memset(mem,-1,sizeof(mem));
dfs(n,-1,0);
/*iloop(n+1){
cout<<depth[i]<<" ";
}
cout<<endl;
iloop(n){
jloop(19){
cout<<mem[i][j]<<" ";
}
cout<<endl;
}*/
//depth[n]=INT_MAX;
iloop(q){
int a,b;
cin>>a>>b;
a--;
if(c[a]>=b){
cout<<a+1<<endl;
continue;
}
int s=a;
for(int i=19;i>=0;i--){
int temp=-1;
if(a!=-1) temp=mem[a][i];
if(range(s,temp)<b){
a=temp;
}
}
if(a==-1 or mem[a][0]==-1){
cout<<0<<endl;
} else{
cout<<mem[a][0]+1<<endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19036 KB |
Output is correct |
| 2 |
Correct |
5 ms |
19036 KB |
Output is correct |
| 3 |
Correct |
5 ms |
19140 KB |
Output is correct |
| 4 |
Correct |
5 ms |
19032 KB |
Output is correct |
| 5 |
Correct |
5 ms |
19032 KB |
Output is correct |
| 6 |
Correct |
6 ms |
19036 KB |
Output is correct |
| 7 |
Correct |
5 ms |
19136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
31724 KB |
Output is correct |
| 2 |
Correct |
149 ms |
30840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19036 KB |
Output is correct |
| 2 |
Correct |
5 ms |
19036 KB |
Output is correct |
| 3 |
Correct |
5 ms |
19140 KB |
Output is correct |
| 4 |
Correct |
5 ms |
19032 KB |
Output is correct |
| 5 |
Correct |
5 ms |
19032 KB |
Output is correct |
| 6 |
Correct |
6 ms |
19036 KB |
Output is correct |
| 7 |
Correct |
5 ms |
19136 KB |
Output is correct |
| 8 |
Correct |
144 ms |
31724 KB |
Output is correct |
| 9 |
Correct |
149 ms |
30840 KB |
Output is correct |
| 10 |
Correct |
5 ms |
19032 KB |
Output is correct |
| 11 |
Correct |
62 ms |
23376 KB |
Output is correct |
| 12 |
Correct |
202 ms |
32848 KB |
Output is correct |
| 13 |
Correct |
164 ms |
26960 KB |
Output is correct |
| 14 |
Correct |
100 ms |
25508 KB |
Output is correct |
| 15 |
Correct |
81 ms |
25804 KB |
Output is correct |
