// Esti <3
//\
šťastia pre nás :)
// you're already the best
// _
// ^ ^ //
// >(O_O)<___//
// \ __ __ \
// \\ \\ \\\\
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3","unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
using ll = long long;
#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = 1e18;
const int mod = 1e9+7;//998244353;
// \
\
:smiling_face_with_3_hearts: :smiling_face_with_3_hearts: :smiling_face_with_3_hearts:
//vidime sa veľmi skoro, moje slnko
const int N=1e5+5;
const int K=18;
int go[N][K];
int up[N][K];
void solve() {
int n, q; cin>>n>>q;
vector<pi> a(n);
forn(i,n) cin>>a[i].f>>a[i].s;
vector<int> to(n);
vector<pi> st;
st.pb({inf,-1});
for(int i=n-1; i>=0; --i) {
while (a[i].f >= st.back().f) st.pop_back();
to[i]=st.back().s;
st.pb({a[i].f,i});
}
forn(i,n) go[i][0]=a[i].s;// + (to[i]!=-1)?a[to[i]].s:inf;
forn(i,n) up[i][0]=to[i];
const int inf=2e9;
for (int j=1; j<K; ++j) {
forn(i,n) go[i][j]=go[i][j-1]+((up[i][j-1]!=-1)?go[up[i][j-1]][j-1]:inf);
forn(i,n) up[i][j]=(up[i][j-1]!=-1)?up[up[i][j-1]][j-1]:up[i][j-1];
}
forn(j,4) {
//forn(i,n) cout<<go[i][j]<<' '; cout<<'\n';
}
//cout<<'\n';
forn(j,4) {
//forn(i,n) cout<<up[i][j]<<' '; cout<<'\n';
}
forn(i,q) {
int r,v; cin>>r>>v; --r;
if (a[r].s >= v) {
cout<<r+1<<'\n'; continue;
}
int z=0;
for (int j=K-1; j>=0; --j) {
if (r==-1) continue;
if (go[r][j] > v) continue;
//cout<<"! "<<r<<' '<<j<<' '<<v<<' '<<go[r][j]<<' '<<up[r][j]<<'\n';
v-=go[r][j];
r=up[r][j];
//cout<<r<<' '<<v<<'\n';
}
//if (v) cout<<to[v]+1<<'\n';
//else
cout<<r+1<<'\n';
}
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while (t--) solve();
return 0;
}
Compilation message
fountain.cpp:3:1: warning: multi-line comment [-Wcomment]
3 | //\
| ^
fountain.cpp:9:1: warning: multi-line comment [-Wcomment]
9 | // \ __ __ \
| ^
fountain.cpp:36:1: warning: multi-line comment [-Wcomment]
36 | // \
| ^
fountain.cpp: In function 'void solve()':
fountain.cpp:83:7: warning: unused variable 'z' [-Wunused-variable]
83 | int z=0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
31684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
