// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
using db = long double;
template<class T> using pq = priority_queue<T, V<T>, less<T>>;
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 19;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, Q; cin >> N >> Q;
vl A(N), B(N); for(int i = 0; i < N; i++) {
cin >> A[i] >> B[i];
}
vi I(N); iota(begin(I), end(I), 0);
sort(begin(I), end(I), [&](int a, int b) {
return A[a] > A[b];
});
V<V<array<ll, 3>>> QQ(N); vi ans(Q);
auto find = [&](ll x) {
int lo = -1, hi = N - 1;
while(lo < hi) {
int mid = (lo + hi + 1) / 2;
if (x <= A[I[mid]]) lo = mid;
else hi = mid - 1;
}
return lo;
};
for(int i = 0; i < Q; i++) {
ll a, b, c; cin >> a >> b >> c;
// cout << a << " " << b << " " << c << endl;
// c-query
int cq = find(a);
if (cq != -1) {
QQ[cq].pb({c, 1, i});
// cout << i << " " << cq << endl;
}
// everything after is a b-query
int bq = min(find(c - b), cq);
if (bq != -1) {
QQ[bq].pb({c, -1, i});
QQ[bq].pb({b, 0, i});
// cout << i << " " << bq << endl;
}
}
// cout << endl;
iset<pl> ct, bt;
for(int i = 0; i < N; i++) {
ct.insert(mp(A[I[i]] + B[I[i]], i));
bt.insert(mp(B[I[i]], i));
// cout << i << endl;
for(auto q : QQ[i]) {
if (q[1] == 0) {
ans[q[2]] += int(sz(bt) - bt.order_of_key(mp(q[0], -MOD)));
// cout << q[2] << " " << q[1] << " " << int(sz(bt) - bt.order_of_key(mp(q[0], -MOD))) << endl;
} else {
ans[q[2]] += q[1] * int(sz(ct) - ct.order_of_key(mp(q[0], -MOD)));
// cout << "> " << sz(ct) << " " << ct.order_of_key(mp(q[0], -MOD)) << endl;
// cout << q[2] << " " << q[1] << " " << q[1] * int(sz(ct) - ct.order_of_key(mp(q[0], -MOD))) << endl;
}
}
// cout << endl;
}
for(int i = 0; i < Q; i++) cout << ans[i] << endl;
exit(0-0);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
7 ms |
1116 KB |
Output is correct |
8 |
Correct |
7 ms |
1076 KB |
Output is correct |
9 |
Correct |
7 ms |
1116 KB |
Output is correct |
10 |
Correct |
7 ms |
1116 KB |
Output is correct |
11 |
Correct |
6 ms |
1156 KB |
Output is correct |
12 |
Correct |
6 ms |
1112 KB |
Output is correct |
13 |
Correct |
7 ms |
1116 KB |
Output is correct |
14 |
Correct |
7 ms |
1316 KB |
Output is correct |
15 |
Correct |
7 ms |
1116 KB |
Output is correct |
16 |
Correct |
6 ms |
1104 KB |
Output is correct |
17 |
Correct |
7 ms |
1048 KB |
Output is correct |
18 |
Correct |
6 ms |
1012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
318 ms |
29096 KB |
Output is correct |
2 |
Correct |
316 ms |
28940 KB |
Output is correct |
3 |
Correct |
343 ms |
28968 KB |
Output is correct |
4 |
Correct |
268 ms |
29040 KB |
Output is correct |
5 |
Correct |
245 ms |
25232 KB |
Output is correct |
6 |
Correct |
232 ms |
25356 KB |
Output is correct |
7 |
Correct |
334 ms |
28420 KB |
Output is correct |
8 |
Correct |
315 ms |
29040 KB |
Output is correct |
9 |
Correct |
312 ms |
28500 KB |
Output is correct |
10 |
Correct |
218 ms |
22780 KB |
Output is correct |
11 |
Correct |
282 ms |
29492 KB |
Output is correct |
12 |
Correct |
259 ms |
19648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
318 ms |
29096 KB |
Output is correct |
2 |
Correct |
316 ms |
28940 KB |
Output is correct |
3 |
Correct |
343 ms |
28968 KB |
Output is correct |
4 |
Correct |
268 ms |
29040 KB |
Output is correct |
5 |
Correct |
245 ms |
25232 KB |
Output is correct |
6 |
Correct |
232 ms |
25356 KB |
Output is correct |
7 |
Correct |
334 ms |
28420 KB |
Output is correct |
8 |
Correct |
315 ms |
29040 KB |
Output is correct |
9 |
Correct |
312 ms |
28500 KB |
Output is correct |
10 |
Correct |
218 ms |
22780 KB |
Output is correct |
11 |
Correct |
282 ms |
29492 KB |
Output is correct |
12 |
Correct |
259 ms |
19648 KB |
Output is correct |
13 |
Correct |
352 ms |
26628 KB |
Output is correct |
14 |
Correct |
348 ms |
28460 KB |
Output is correct |
15 |
Correct |
310 ms |
29004 KB |
Output is correct |
16 |
Correct |
308 ms |
28168 KB |
Output is correct |
17 |
Correct |
249 ms |
22800 KB |
Output is correct |
18 |
Correct |
242 ms |
25252 KB |
Output is correct |
19 |
Correct |
347 ms |
26724 KB |
Output is correct |
20 |
Correct |
378 ms |
27904 KB |
Output is correct |
21 |
Correct |
360 ms |
25464 KB |
Output is correct |
22 |
Correct |
220 ms |
22152 KB |
Output is correct |
23 |
Correct |
277 ms |
28912 KB |
Output is correct |
24 |
Correct |
285 ms |
20460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
7 ms |
1116 KB |
Output is correct |
8 |
Correct |
7 ms |
1076 KB |
Output is correct |
9 |
Correct |
7 ms |
1116 KB |
Output is correct |
10 |
Correct |
7 ms |
1116 KB |
Output is correct |
11 |
Correct |
6 ms |
1156 KB |
Output is correct |
12 |
Correct |
6 ms |
1112 KB |
Output is correct |
13 |
Correct |
7 ms |
1116 KB |
Output is correct |
14 |
Correct |
7 ms |
1316 KB |
Output is correct |
15 |
Correct |
7 ms |
1116 KB |
Output is correct |
16 |
Correct |
6 ms |
1104 KB |
Output is correct |
17 |
Correct |
7 ms |
1048 KB |
Output is correct |
18 |
Correct |
6 ms |
1012 KB |
Output is correct |
19 |
Correct |
318 ms |
29096 KB |
Output is correct |
20 |
Correct |
316 ms |
28940 KB |
Output is correct |
21 |
Correct |
343 ms |
28968 KB |
Output is correct |
22 |
Correct |
268 ms |
29040 KB |
Output is correct |
23 |
Correct |
245 ms |
25232 KB |
Output is correct |
24 |
Correct |
232 ms |
25356 KB |
Output is correct |
25 |
Correct |
334 ms |
28420 KB |
Output is correct |
26 |
Correct |
315 ms |
29040 KB |
Output is correct |
27 |
Correct |
312 ms |
28500 KB |
Output is correct |
28 |
Correct |
218 ms |
22780 KB |
Output is correct |
29 |
Correct |
282 ms |
29492 KB |
Output is correct |
30 |
Correct |
259 ms |
19648 KB |
Output is correct |
31 |
Correct |
352 ms |
26628 KB |
Output is correct |
32 |
Correct |
348 ms |
28460 KB |
Output is correct |
33 |
Correct |
310 ms |
29004 KB |
Output is correct |
34 |
Correct |
308 ms |
28168 KB |
Output is correct |
35 |
Correct |
249 ms |
22800 KB |
Output is correct |
36 |
Correct |
242 ms |
25252 KB |
Output is correct |
37 |
Correct |
347 ms |
26724 KB |
Output is correct |
38 |
Correct |
378 ms |
27904 KB |
Output is correct |
39 |
Correct |
360 ms |
25464 KB |
Output is correct |
40 |
Correct |
220 ms |
22152 KB |
Output is correct |
41 |
Correct |
277 ms |
28912 KB |
Output is correct |
42 |
Correct |
285 ms |
20460 KB |
Output is correct |
43 |
Correct |
339 ms |
26476 KB |
Output is correct |
44 |
Correct |
369 ms |
26692 KB |
Output is correct |
45 |
Correct |
368 ms |
28520 KB |
Output is correct |
46 |
Correct |
411 ms |
28312 KB |
Output is correct |
47 |
Correct |
250 ms |
22940 KB |
Output is correct |
48 |
Correct |
216 ms |
22072 KB |
Output is correct |
49 |
Correct |
384 ms |
28112 KB |
Output is correct |
50 |
Correct |
346 ms |
25132 KB |
Output is correct |
51 |
Correct |
369 ms |
27800 KB |
Output is correct |
52 |
Correct |
230 ms |
20424 KB |
Output is correct |
53 |
Correct |
338 ms |
28840 KB |
Output is correct |