#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>
using namespace std;
const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const int lg = 20;
const long long inf = 1e18;
signed main()
{
ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
int tt=1;
//cin >> tt;
while(tt--)
{
int n,q;
cin >> n >> q;
vector<pii> niz(n);
vector<int> prefmx(n+1, 0);
vector<vector<int>>sm(lg, vector<int>(n,0));
vector<vector<int>>nxt(lg, vector<int>(n,-1));
for(int i=0; i<n; i++)
{
cin >> niz[i].fi >> niz[i].sc;
prefmx[i+1] = max(prefmx[i], niz[i].fi);
sm[0][i] = niz[i].sc;
}
for(int i=0; i<n-1; i++)
{
int l = i+1; int r = n;
int rez = n;
while(l<=r)
{
int mid = l+r>>1;
if(prefmx[mid+1] > niz[i].fi)
{
rez = mid;
r = mid-1;
}
else
{
l= mid+1;
}
}
if(rez==n)continue;
nxt[0][i] = rez;
}
for(int i=1; i<lg; i++)
{
for(int j=0; j<n; j++)
{
if(nxt[i-1][j] == -1)nxt[i][j] = -1;
else nxt[i][j] = nxt[i-1][nxt[i-1][j]];
}
}
for(int i=1; i<lg; i++)
{
for(int j=0; j<n; j++)
{
if(nxt[i-1][j] == -1)sm[i][j] = sm[i-1][j];
else sm[i][j] = sm[i-1][j] + sm[i-1][nxt[i-1][j]];
}
}
for(int i=0; i<3; i++)
{
for(int j=0; j<n; j++)cout << sm[i][j] << " ";cout << endl;
}
while(q--)
{
int a,b;
cin >> a >> b;
a--;
int rez = a;
if(b <= niz[a].sc)
{
cout << a+1 << endl;
continue;
}
for(int i=lg-1; i>=1; i--)
{
if(a==-1)break;
if(sm[i][a] < b)
{
b-= sm[i][a];
a = nxt[i-1][a];
}
else continue;
}
if(a==-1)rez = -1;
else rez = nxt[0][a];
cout << rez + 1 << endl;
}
}
}
/*
6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8
*/
Compilation message
fountain.cpp: In function 'int main()':
fountain.cpp:43:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = l+r>>1;
| ~^~
fountain.cpp:75:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
75 | for(int j=0; j<n; j++)cout << sm[i][j] << " ";cout << endl;
| ^~~
fountain.cpp:75:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
75 | for(int j=0; j<n; j++)cout << sm[i][j] << " ";cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
38000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
