#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll n,q;
cin >> n >> q;
vector<pair<ll , ll>> v;
stack<ll> s;
ll p[n];
for (ll i=0; n>i; i++)
{
p[i] = 0;
}
ll sum[n];
for (ll i=0; n>i; i++)
{
ll a,b;
cin >> a >> b;
v.push_back({a , b});
sum[i] = v[i].second;
}
for (ll i=n-1; i>=0; i--)
{
while (!s.empty() && v[i].first > v[s.top()].first)
{
s.pop();
}
if (s.empty())
{
p[i] = -1;
}
else
{
p[i] = s.top();
}
s.push(i);
}
for (ll i=n-1; i>=0; i--)
{
if (p[i] != -1)
{
sum[i] += sum[p[i]];
}
}
while (q--)
{
ll a,b;
cin >> a >> b;
a--;
if (b > sum[a])
{
cout << 0 << endl;
}
else
{
while (b > 0)
{
b -= v[a].second;
if (0 >= b)
{
cout << a + 1 << endl;
break;
}
a = p[a];
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1585 ms |
4328 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
