This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//amira
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define f first
#define s second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define pll pair <ll,ll>
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int M = 1e9+7;
const int N = 1e5 + 111;
const ll INF = 1e10 + 1;
const int K = 205;
ll n,q,d[N],w[N],nxt[N];
int main() {
#ifdef MM
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
stack <ll> st;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> d[i] >> w[i];
}
for (int i = n; i >= 1; i--) {
while (!st.empty() && d[st.top()] <= d[i]) {
st.pop();
}
if (st.empty()) nxt[i] = n + 1;
else nxt[i] = st.top();
st.push(i);
}
for (int i = 1; i <= q; i++) {
ll id,l;
cin >> id >> l;
ll final = id, cur = id; //cout << "case " << i << endl;
while (cur < n + 1 && w[cur] < l) {
l -= w[cur];
cur = nxt[cur];
//cout << l << ' ' << cur << endl;
}
if (cur == n + 1) cout << 0 << endl;
else cout << cur << endl;
}
return 0;
}
Compilation message (stderr)
fountain.cpp: In function 'int main()':
fountain.cpp:42:6: warning: unused variable 'final' [-Wunused-variable]
42 | ll final = id, cur = id; //cout << "case " << i << endl;
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |