/**
MAYBE THERE'S ONLY A DARK ROAD UP AHEAD.
BUT YOU still HAVE TO BELIEVE AND KEEP GOING.
BELIEVE THAT THE STARS WILL LIGHT YOUR PATH,
EVEN A LITTLE BIT. COME ON...
LET'S go on A JOURNEY!
**/
#include <bits/stdc++.h>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 1e5 + 5;
int n, m, ans[N], inf = 1e9, sz[2] = {1, 1};
struct asd {
int x, y, z, in;
};
asd a[N], b[N];
struct tree {
int l, r, val;
};
tree t[2][N * 30];
void update (int ad, int pos, int v = 1, int tl = 0, int tr = inf) {
if (tl == tr)
t[ad][v].val++;
else {
int tm = (tl + tr) >> 1;
if (pos <= tm) {
if (!t[ad][v].l) t[ad][v].l = ++sz[ad];
update(ad, pos, t[ad][v].l, tl, tm);
}
else {
if (!t[ad][v].r) t[ad][v].r = ++sz[ad];
update(ad, pos, t[ad][v].r, tm + 1, tr);
}
t[ad][v].val = t[ad][ t[ad][v].l ].val + t[ad][ t[ad][v].r ].val;
}
}
bool cmp (asd x, asd y) {
return x.z > y.z;
}
int get (int ad, int l, int r, int v = 1, int tl = 0, int tr = inf) {
if (l > r || tl > r || l > tr || v == 0)
return 0;
if (l <= tl && tr <= r)
return t[ad][v].val;
int tm = (tl + tr) >> 1;
return get( ad, l, r, t[ad][v].l, tl, tm ) + get( ad, l, r, t[ad][v].r, tm + 1, tr );
}
main(){
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &a[i].x, &a[i].y);
a[i].z = a[i].x + a[i].y;
}
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z);
b[i].z = max( b[i].z, b[i].x + b[i].y );
b[i].in = i;
}
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + m + 1, cmp);
int j = 1;
for (int i = 1; i <= m; i++) {
while (j <= n && a[j].z >= b[i].z) {
update(0, a[j].x);
update(1, a[j].y);
j++;
}
//cout << b[i].z << " " << get(1, 0, b[i].y - 1) << endl;
ans[b[i].in] = j - get(0, 0, b[i].x - 1) - get(1, 0, b[i].y - 1) - 1;
}
for (int i = 1; i <= m; i++) {
printf("%d\n", ans[i]);
}
}
Compilation message
examination.cpp:65:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
examination.cpp: In function 'int main()':
examination.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a[i].x, &a[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
372 KB |
Output is correct |
7 |
Correct |
11 ms |
1912 KB |
Output is correct |
8 |
Correct |
11 ms |
1912 KB |
Output is correct |
9 |
Correct |
11 ms |
2040 KB |
Output is correct |
10 |
Correct |
11 ms |
1272 KB |
Output is correct |
11 |
Correct |
9 ms |
1272 KB |
Output is correct |
12 |
Correct |
7 ms |
504 KB |
Output is correct |
13 |
Correct |
12 ms |
2040 KB |
Output is correct |
14 |
Correct |
11 ms |
2040 KB |
Output is correct |
15 |
Correct |
13 ms |
1912 KB |
Output is correct |
16 |
Correct |
9 ms |
1272 KB |
Output is correct |
17 |
Correct |
9 ms |
1272 KB |
Output is correct |
18 |
Correct |
6 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
285 ms |
9212 KB |
Output is correct |
2 |
Correct |
270 ms |
9080 KB |
Output is correct |
3 |
Correct |
278 ms |
9208 KB |
Output is correct |
4 |
Correct |
211 ms |
7416 KB |
Output is correct |
5 |
Correct |
214 ms |
7468 KB |
Output is correct |
6 |
Correct |
178 ms |
5496 KB |
Output is correct |
7 |
Correct |
270 ms |
9200 KB |
Output is correct |
8 |
Correct |
265 ms |
9208 KB |
Output is correct |
9 |
Correct |
259 ms |
9208 KB |
Output is correct |
10 |
Correct |
197 ms |
7160 KB |
Output is correct |
11 |
Correct |
197 ms |
7204 KB |
Output is correct |
12 |
Correct |
125 ms |
5032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
285 ms |
9212 KB |
Output is correct |
2 |
Correct |
270 ms |
9080 KB |
Output is correct |
3 |
Correct |
278 ms |
9208 KB |
Output is correct |
4 |
Correct |
211 ms |
7416 KB |
Output is correct |
5 |
Correct |
214 ms |
7468 KB |
Output is correct |
6 |
Correct |
178 ms |
5496 KB |
Output is correct |
7 |
Correct |
270 ms |
9200 KB |
Output is correct |
8 |
Correct |
265 ms |
9208 KB |
Output is correct |
9 |
Correct |
259 ms |
9208 KB |
Output is correct |
10 |
Correct |
197 ms |
7160 KB |
Output is correct |
11 |
Correct |
197 ms |
7204 KB |
Output is correct |
12 |
Correct |
125 ms |
5032 KB |
Output is correct |
13 |
Correct |
271 ms |
9188 KB |
Output is correct |
14 |
Correct |
281 ms |
9208 KB |
Output is correct |
15 |
Correct |
276 ms |
9336 KB |
Output is correct |
16 |
Correct |
210 ms |
7388 KB |
Output is correct |
17 |
Correct |
222 ms |
7416 KB |
Output is correct |
18 |
Correct |
187 ms |
5496 KB |
Output is correct |
19 |
Correct |
265 ms |
9080 KB |
Output is correct |
20 |
Correct |
273 ms |
9208 KB |
Output is correct |
21 |
Correct |
258 ms |
9208 KB |
Output is correct |
22 |
Correct |
198 ms |
7132 KB |
Output is correct |
23 |
Correct |
197 ms |
7152 KB |
Output is correct |
24 |
Correct |
125 ms |
5036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
372 KB |
Output is correct |
7 |
Correct |
11 ms |
1912 KB |
Output is correct |
8 |
Correct |
11 ms |
1912 KB |
Output is correct |
9 |
Correct |
11 ms |
2040 KB |
Output is correct |
10 |
Correct |
11 ms |
1272 KB |
Output is correct |
11 |
Correct |
9 ms |
1272 KB |
Output is correct |
12 |
Correct |
7 ms |
504 KB |
Output is correct |
13 |
Correct |
12 ms |
2040 KB |
Output is correct |
14 |
Correct |
11 ms |
2040 KB |
Output is correct |
15 |
Correct |
13 ms |
1912 KB |
Output is correct |
16 |
Correct |
9 ms |
1272 KB |
Output is correct |
17 |
Correct |
9 ms |
1272 KB |
Output is correct |
18 |
Correct |
6 ms |
504 KB |
Output is correct |
19 |
Correct |
285 ms |
9212 KB |
Output is correct |
20 |
Correct |
270 ms |
9080 KB |
Output is correct |
21 |
Correct |
278 ms |
9208 KB |
Output is correct |
22 |
Correct |
211 ms |
7416 KB |
Output is correct |
23 |
Correct |
214 ms |
7468 KB |
Output is correct |
24 |
Correct |
178 ms |
5496 KB |
Output is correct |
25 |
Correct |
270 ms |
9200 KB |
Output is correct |
26 |
Correct |
265 ms |
9208 KB |
Output is correct |
27 |
Correct |
259 ms |
9208 KB |
Output is correct |
28 |
Correct |
197 ms |
7160 KB |
Output is correct |
29 |
Correct |
197 ms |
7204 KB |
Output is correct |
30 |
Correct |
125 ms |
5032 KB |
Output is correct |
31 |
Correct |
271 ms |
9188 KB |
Output is correct |
32 |
Correct |
281 ms |
9208 KB |
Output is correct |
33 |
Correct |
276 ms |
9336 KB |
Output is correct |
34 |
Correct |
210 ms |
7388 KB |
Output is correct |
35 |
Correct |
222 ms |
7416 KB |
Output is correct |
36 |
Correct |
187 ms |
5496 KB |
Output is correct |
37 |
Correct |
265 ms |
9080 KB |
Output is correct |
38 |
Correct |
273 ms |
9208 KB |
Output is correct |
39 |
Correct |
258 ms |
9208 KB |
Output is correct |
40 |
Correct |
198 ms |
7132 KB |
Output is correct |
41 |
Correct |
197 ms |
7152 KB |
Output is correct |
42 |
Correct |
125 ms |
5036 KB |
Output is correct |
43 |
Correct |
367 ms |
39416 KB |
Output is correct |
44 |
Correct |
366 ms |
39416 KB |
Output is correct |
45 |
Correct |
426 ms |
39416 KB |
Output is correct |
46 |
Correct |
242 ms |
22392 KB |
Output is correct |
47 |
Correct |
243 ms |
22480 KB |
Output is correct |
48 |
Correct |
155 ms |
5248 KB |
Output is correct |
49 |
Correct |
394 ms |
39300 KB |
Output is correct |
50 |
Correct |
355 ms |
39544 KB |
Output is correct |
51 |
Correct |
365 ms |
39288 KB |
Output is correct |
52 |
Correct |
225 ms |
22264 KB |
Output is correct |
53 |
Correct |
242 ms |
22264 KB |
Output is correct |