#include <bits/stdc++.h>
#define N 200005
#define M 1000000007
using namespace std;
using ll = long long;
struct ImplicitSegTree {
struct Node {
ll val;
Node *lft, *rgt;;
Node() : val(0), lft(nullptr), rgt(nullptr) {}
void push() {
if (!lft) lft = new Node();
if (!rgt) rgt = new Node();
}
void update(ll l, ll r, ll idx) {
++val;
if (l == r) return;
push();
ll m = (l+r) / 2;
if (idx <= m) lft->update(l, m, idx);
else rgt->update(m+1, r, idx);
}
ll query(ll l, ll r, ll lq, ll rq) {
if (r < lq || rq < l) return 0;
if (lq <= l && r <= rq) return val;
push();
ll m = (l+r) / 2;
return (
lft->query(l, m, lq, rq) +
rgt->query(m+1, r, lq, rq)
);
}
};
ll n;
vector<Node> nodes;
ImplicitSegTree(ll n) : n(n), nodes() {
nodes.emplace_back();
}
void update(ll idx) {
nodes[0].update(0, n, idx);
}
ll query(ll l, ll r) {
return nodes[0].query(0, n, l, r);
}
};
struct Query {
ll a, b, c, idx;
bool operator<(Query rhs) const {
if (c == rhs.c) return idx < rhs.idx;
else return c > rhs.c;
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
ll n, q; cin>>n>>q;
vector<Query> qs;
for (int i=0; i<n; i++) {
int x, y; cin>>x>>y;
qs.push_back({x, y, x+y, -1});
}
for (int i=0; i<q; i++) {
int a, b, c; cin>>a>>b>>c;
c = max(c, a+b);
qs.push_back({a, b, c, i});
}
sort(qs.begin(), qs.end());
ImplicitSegTree sega(M), segb(M);
vector<ll> ans(q);
ll cnt = 0;
for (auto [a, b, c, idx] : qs) {
if (idx == -1) { // point
sega.update(a);
segb.update(b);
++cnt;
} else { // query
ll aq = sega.query(0, a-1);
ll bq = segb.query(0, b-1);
ans[idx] = cnt - aq - bq;
}
}
for (ll x : ans) cout<<x<<endl;
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:90:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
90 | for (auto [a, b, c, idx] : qs) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
29 ms |
13376 KB |
Output is correct |
8 |
Correct |
28 ms |
13368 KB |
Output is correct |
9 |
Correct |
28 ms |
13428 KB |
Output is correct |
10 |
Correct |
18 ms |
6980 KB |
Output is correct |
11 |
Correct |
18 ms |
6992 KB |
Output is correct |
12 |
Correct |
9 ms |
708 KB |
Output is correct |
13 |
Correct |
28 ms |
13404 KB |
Output is correct |
14 |
Correct |
32 ms |
13328 KB |
Output is correct |
15 |
Correct |
31 ms |
13316 KB |
Output is correct |
16 |
Correct |
17 ms |
6992 KB |
Output is correct |
17 |
Correct |
17 ms |
6916 KB |
Output is correct |
18 |
Correct |
8 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
386 ms |
22572 KB |
Output is correct |
2 |
Correct |
384 ms |
22564 KB |
Output is correct |
3 |
Correct |
384 ms |
22632 KB |
Output is correct |
4 |
Correct |
309 ms |
15736 KB |
Output is correct |
5 |
Correct |
295 ms |
15760 KB |
Output is correct |
6 |
Correct |
266 ms |
9400 KB |
Output is correct |
7 |
Correct |
361 ms |
22212 KB |
Output is correct |
8 |
Correct |
390 ms |
22260 KB |
Output is correct |
9 |
Correct |
345 ms |
21884 KB |
Output is correct |
10 |
Correct |
292 ms |
15504 KB |
Output is correct |
11 |
Correct |
278 ms |
15512 KB |
Output is correct |
12 |
Correct |
252 ms |
9348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
386 ms |
22572 KB |
Output is correct |
2 |
Correct |
384 ms |
22564 KB |
Output is correct |
3 |
Correct |
384 ms |
22632 KB |
Output is correct |
4 |
Correct |
309 ms |
15736 KB |
Output is correct |
5 |
Correct |
295 ms |
15760 KB |
Output is correct |
6 |
Correct |
266 ms |
9400 KB |
Output is correct |
7 |
Correct |
361 ms |
22212 KB |
Output is correct |
8 |
Correct |
390 ms |
22260 KB |
Output is correct |
9 |
Correct |
345 ms |
21884 KB |
Output is correct |
10 |
Correct |
292 ms |
15504 KB |
Output is correct |
11 |
Correct |
278 ms |
15512 KB |
Output is correct |
12 |
Correct |
252 ms |
9348 KB |
Output is correct |
13 |
Correct |
397 ms |
23156 KB |
Output is correct |
14 |
Correct |
384 ms |
22908 KB |
Output is correct |
15 |
Correct |
382 ms |
22596 KB |
Output is correct |
16 |
Correct |
314 ms |
16132 KB |
Output is correct |
17 |
Correct |
303 ms |
16244 KB |
Output is correct |
18 |
Correct |
270 ms |
9400 KB |
Output is correct |
19 |
Correct |
403 ms |
23008 KB |
Output is correct |
20 |
Correct |
407 ms |
22932 KB |
Output is correct |
21 |
Correct |
397 ms |
22824 KB |
Output is correct |
22 |
Correct |
279 ms |
15580 KB |
Output is correct |
23 |
Correct |
281 ms |
15584 KB |
Output is correct |
24 |
Correct |
267 ms |
9356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
29 ms |
13376 KB |
Output is correct |
8 |
Correct |
28 ms |
13368 KB |
Output is correct |
9 |
Correct |
28 ms |
13428 KB |
Output is correct |
10 |
Correct |
18 ms |
6980 KB |
Output is correct |
11 |
Correct |
18 ms |
6992 KB |
Output is correct |
12 |
Correct |
9 ms |
708 KB |
Output is correct |
13 |
Correct |
28 ms |
13404 KB |
Output is correct |
14 |
Correct |
32 ms |
13328 KB |
Output is correct |
15 |
Correct |
31 ms |
13316 KB |
Output is correct |
16 |
Correct |
17 ms |
6992 KB |
Output is correct |
17 |
Correct |
17 ms |
6916 KB |
Output is correct |
18 |
Correct |
8 ms |
716 KB |
Output is correct |
19 |
Correct |
386 ms |
22572 KB |
Output is correct |
20 |
Correct |
384 ms |
22564 KB |
Output is correct |
21 |
Correct |
384 ms |
22632 KB |
Output is correct |
22 |
Correct |
309 ms |
15736 KB |
Output is correct |
23 |
Correct |
295 ms |
15760 KB |
Output is correct |
24 |
Correct |
266 ms |
9400 KB |
Output is correct |
25 |
Correct |
361 ms |
22212 KB |
Output is correct |
26 |
Correct |
390 ms |
22260 KB |
Output is correct |
27 |
Correct |
345 ms |
21884 KB |
Output is correct |
28 |
Correct |
292 ms |
15504 KB |
Output is correct |
29 |
Correct |
278 ms |
15512 KB |
Output is correct |
30 |
Correct |
252 ms |
9348 KB |
Output is correct |
31 |
Correct |
397 ms |
23156 KB |
Output is correct |
32 |
Correct |
384 ms |
22908 KB |
Output is correct |
33 |
Correct |
382 ms |
22596 KB |
Output is correct |
34 |
Correct |
314 ms |
16132 KB |
Output is correct |
35 |
Correct |
303 ms |
16244 KB |
Output is correct |
36 |
Correct |
270 ms |
9400 KB |
Output is correct |
37 |
Correct |
403 ms |
23008 KB |
Output is correct |
38 |
Correct |
407 ms |
22932 KB |
Output is correct |
39 |
Correct |
397 ms |
22824 KB |
Output is correct |
40 |
Correct |
279 ms |
15580 KB |
Output is correct |
41 |
Correct |
281 ms |
15584 KB |
Output is correct |
42 |
Correct |
267 ms |
9356 KB |
Output is correct |
43 |
Correct |
935 ms |
311560 KB |
Output is correct |
44 |
Correct |
925 ms |
311632 KB |
Output is correct |
45 |
Correct |
949 ms |
311564 KB |
Output is correct |
46 |
Correct |
529 ms |
160568 KB |
Output is correct |
47 |
Correct |
521 ms |
160508 KB |
Output is correct |
48 |
Correct |
267 ms |
9400 KB |
Output is correct |
49 |
Correct |
888 ms |
300188 KB |
Output is correct |
50 |
Correct |
916 ms |
300332 KB |
Output is correct |
51 |
Correct |
873 ms |
288804 KB |
Output is correct |
52 |
Correct |
505 ms |
160384 KB |
Output is correct |
53 |
Correct |
477 ms |
159528 KB |
Output is correct |