#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define endl '\n'
#define all(v) v.begin(), v.end()
#define all1(v) v.begin() + 1, v.end()
#define rall1(v) v.rbegin(), v.rend()-1
#define fr(m,n,k) for(int m=n;m<=k;m++)
#define frr(m,n,k) for(int m=n;m>=k;m--)
#define yes cout << "YES"
#define no cout << "NO"
#define yesm cout << "Yes"
#define nom cout << "No"
#define inf 1e18
#define ext {cout << -1; return;}
#define zxt {cout << 0; return;}
#define noxt {no;return;}
#define yesxt {yes;return;}
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define rall(a) a.rbegin(),a.rend()
#define fill(x,s) memset(x, s, sizeof(x));
#define lb lower_bound
#define ub upper_bound
#define pi pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vc vector<char>
#define vb vector<bool>
#define vs vector<string>
#define vpi vector<pi>
#define mii map<int,int>
#define mivi map<int,vi>
#define mci map<char,int>
#define als(i) cout << i.fi << " " << i.se << endl
#define si set<int>
#define msi multiset<int>
#define fi first
#define wq while(q--)
#define se second
#define sz size()
#define el cout<<endl
const int mod = 1e9 + 7;
// const int mod = 998244353;
int fac(int n) {int ans = 1; for (int i = 1; i <= n; ++i) {ans = ans * i % mod;} return ans;}
int binpow(int x, int y) {if (y == 0) return 1; int z = 1; while (y) { if (y & 1) z = z * x % mod; x = x * x % mod; y >>= 1;} return z;}
int inv(int x) {return binpow(x, mod - 2);}
int bintoint(string s) {reverse(all(s)); int xx = 0; int m = 1; int z = s.sz; fr(j, 0, z) {xx += (s[j] == '1' ? m : 0); m <<= 1;} return xx;}
string inttobin(int x) {if (x == 0) return "0"; string s; while (x) {s += (x & 1) + '0'; x >>= 1;} reverse(all(s)); return s;}
int add(int x, int y) {int zz = ((x + y) % mod + mod) % mod; return zz;}
string ads(string s, string p) {if (s.sz > p.sz) swap(s, p); int n = s.sz, m = p.sz; reverse(all(s)); reverse(all(p)); int tm = 0; string st; fr(i, 0, n - 1) {tm = s[i] - '0' + p[i] - '0' + tm; st += '0' + tm % 10; tm /= 10;} fr(i, n, m - 1) {tm = p[i] - '0' + tm; st += '0' + tm % 10; tm /= 10;} if (tm != 0) {st += '0' + tm % 10;} reverse(all(st)); return st;}
bool id, id1, id2;
int n, m, k, l, r, a, b, c, d, e, w, x, y, z, i, j, q, t, o;
int mi = inf, ma, sum, ans, num, cnt;
string s, p;
const int N = 2;
void solve() {
cin >> n >> q; pi pro[n + 1];
fr(i, 1, n) {
cin >> x >> y; pro[i] = {x, y};
}
vi pre(n + 1); ma = 0;
pre[1] = pro[1].se; ma = max(ma, pro[1].fi);
// cout << ma;
fr(i, 2, n) {
auto [x, y] = pro[i];
auto [a, b] = pro[i - 1];
if (x <= a) pre[i] = pre[i - 1];
else pre[i] = pre[i - 1] + y;
// ma = max(ma, x);
}
// fr(i, 1, n) cout << pre[i] << " "; el;
fr(i, 1, q) {
cin >> x >> c;
l = x; r = n; // bisa sampai mana
ans = x - 1;
while (l <= r) {
int m = (l + r) / 2;
if (pre[m] - pre[x] + pro[x].se + 1 <= c) {
ans = m;
l = m + 1;
}
else r = m - 1;
}
// cout << ans << " ";
if (ans == n) {
cout << 0;
}
else cout << ans + 1;
el;
}
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
int T = 1;
// cin >> T;
for (; T--;) {
cout << fixed << setprecision(18); solve();
cout << endl;
} return 0;
}
/*
cari solusi dari : ex tc, pola/dp/brute, dr bentuk soal biasanya pke ap, ganti
jd bentuk lain (lbh kecil mayb, coba 2 or 3), coba asal2 theorem / sort / or ganti2 (ada pola gak)
if TLE (ganti vector ke pq, kecilin range, change ll to int, if compress(
coba pake yg linear jangan yg lb))
check overflow, balik kali jd bagi
check kalo k kecil, check constraint yg kecil
RTE = out of bound / change ll to int / bagi or modulo 0 / endl to '\n'
TULIS !!! / liat sebaliknya / semuanya / sebagian
out of bounds / overflor / array bounds
answer minus, edge test case / special tc
TLE/MLE
check other approach / solusi jangan terlalu ribet
*/
// liat sebaliknya / semuanya / sebagian / case kecil (0,1,2,...)
// liat parity (odd or even) / kalo mod 4 sisa 2 gmn, sisa 3 gmn dll
// out of bounds / overflow / array bounds
// answer minus, edge test case / special tc
// TLE/MLE
// check other approach / solusi jangan terlalu ribet
/*
brute force, greedy,pref sum / xor / factor / prime,2pointer,gcd/lcm,even/odd
,min/max,binsearch, bfs/dfs,iterate,multiple/divisor
DSU, bipartite graph,bitmasking, sliding window,konstanta
divconquer,bitmasking, konstanta,djikstra,stack,queue,scanline
coordinate compression,sparse table,prefix difference,segtree,dp,
*/
// tools :
//__lg(x),__builtinpopcount,nextpermutation(), is_sorted / alpha / digit,
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
3340 KB |
Output is correct |
| 2 |
Correct |
60 ms |
5060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
