#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
vector <ll> id;
ll find(ll i){
if (id[i] <= -1) return i;
return id[i] = find(id[i]);
}
void unio(ll i,ll j){
ll a = find(i);
ll b = find(j);
if (a == b) return;
id[a] += id[b];
id[b] = a;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin >> n;
vector <pair<ll,ll>> arr(n);
id.resize(n,-1);
for (int z=0;z<n;z++){
cin >> arr[z].first >> arr[z].second;
}
for (int z=0;z<n;z++){
if (id[z] >= 0) continue;
ll x1 = arr[z].first-arr[z].second;
ll x2 = arr[z].first+arr[z].second;
for (int x=0;x<n;x++){
if (id[x] >= 0) continue;
ll x3 = arr[x].first-arr[x].second;
ll x4 = arr[x].first+arr[x].second;
if ((x1 <= x3 && x4 <= x2)){
if (id[x] >= 0) continue;
unio(z,x);
}
}
}
ll ans = 0;
for (int z=0;z<n;z++){
if (id[z] < 0) ans++;
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2058 ms |
262144 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
5 |
Correct |
2 ms |
380 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
5 |
Correct |
2 ms |
380 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
5 |
Correct |
2 ms |
380 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
3 ms |
380 KB |
Output is correct |
12 |
Correct |
7 ms |
380 KB |
Output is correct |
13 |
Correct |
10 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
5 |
Correct |
2 ms |
380 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
3 ms |
380 KB |
Output is correct |
12 |
Correct |
7 ms |
380 KB |
Output is correct |
13 |
Correct |
10 ms |
376 KB |
Output is correct |
14 |
Correct |
343 ms |
8304 KB |
Output is correct |
15 |
Correct |
295 ms |
8312 KB |
Output is correct |
16 |
Execution timed out |
2057 ms |
7416 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2023 ms |
262144 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2058 ms |
262144 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |