#include <bits/stdc++.h>
using namespace std;
#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << " "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));
/*
for any given pair it's ez to check
if you can create an edge between them
probably can calc contrib
this way you can quickly check like how many people you can donate this book to?
note that you can only donate to someone else if your e-value is greater than theirs
at the very least
2^n sub is ez
what about n^2 then
you get a dag with each edge existing if i can infl j
ans = # of nodes with indeg 0
*/
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
vector<array<int, 2>> xe(n);
int mne = 1e9 + 1, mxe = -1;
for (int i = 0; i < n; i++) {
cin >> xe[i][0] >> xe[i][1];
mne = min(mne, xe[i][1]);
mxe = max(mxe, xe[i][1]);
}
sort(xe.begin(), xe.end());
auto it = unique(xe.begin(), xe.end());
xe.erase(it, xe.end());
n = (int) xe.size();
if (mne == mxe) {
cout << n << '\n';
return 0;
}
vector<int> indeg(n, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j == i) continue;
if (abs(xe[i][0] - xe[j][0]) <= xe[i][1] - xe[j][1]) {
indeg[j]++;
}
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (!indeg[i]) cnt++;
}
cout << cnt << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
500 KB |
Output is correct |
2 |
Correct |
31 ms |
3636 KB |
Output is correct |
3 |
Correct |
44 ms |
5180 KB |
Output is correct |
4 |
Correct |
110 ms |
13032 KB |
Output is correct |
5 |
Correct |
64 ms |
9264 KB |
Output is correct |
6 |
Correct |
121 ms |
13584 KB |
Output is correct |
7 |
Correct |
128 ms |
14076 KB |
Output is correct |
8 |
Correct |
144 ms |
13904 KB |
Output is correct |
9 |
Correct |
97 ms |
13904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
452 KB |
Output is correct |
8 |
Correct |
0 ms |
500 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
452 KB |
Output is correct |
8 |
Correct |
0 ms |
500 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
3 ms |
344 KB |
Output is correct |
20 |
Correct |
3 ms |
348 KB |
Output is correct |
21 |
Correct |
3 ms |
348 KB |
Output is correct |
22 |
Correct |
3 ms |
348 KB |
Output is correct |
23 |
Correct |
3 ms |
348 KB |
Output is correct |
24 |
Correct |
2 ms |
348 KB |
Output is correct |
25 |
Correct |
2 ms |
348 KB |
Output is correct |
26 |
Correct |
2 ms |
484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
500 KB |
Output is correct |
2 |
Correct |
31 ms |
3636 KB |
Output is correct |
3 |
Correct |
44 ms |
5180 KB |
Output is correct |
4 |
Correct |
110 ms |
13032 KB |
Output is correct |
5 |
Correct |
64 ms |
9264 KB |
Output is correct |
6 |
Correct |
121 ms |
13584 KB |
Output is correct |
7 |
Correct |
128 ms |
14076 KB |
Output is correct |
8 |
Correct |
144 ms |
13904 KB |
Output is correct |
9 |
Correct |
97 ms |
13904 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
452 KB |
Output is correct |
17 |
Correct |
0 ms |
500 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
0 ms |
604 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
3 ms |
344 KB |
Output is correct |
29 |
Correct |
3 ms |
348 KB |
Output is correct |
30 |
Correct |
3 ms |
348 KB |
Output is correct |
31 |
Correct |
3 ms |
348 KB |
Output is correct |
32 |
Correct |
3 ms |
348 KB |
Output is correct |
33 |
Correct |
2 ms |
348 KB |
Output is correct |
34 |
Correct |
2 ms |
348 KB |
Output is correct |
35 |
Correct |
2 ms |
484 KB |
Output is correct |
36 |
Execution timed out |
2094 ms |
11088 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |