Submission #1356165

#TimeUsernameProblemLanguageResultExecution timeMemory
1356165nathlol2Advertisement 2 (JOI23_ho_t2)C++20
59 / 100
2094 ms4628 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, ans, v[N];
pair<int, int> a[N];
tuple<int, int, int> b[N], c[N];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1;i<=n;i++) cin >> a[i].second >> a[i].first;
    sort(a + 1, a + n + 1, greater<pair<int, int>>());
    for(int i = 1;i<=n;i++) b[i] = {a[i].first - a[i].second, a[i].second, i}, c[i] = {a[i].first + a[i].second, a[i].second, i};
    sort(b + 1, b + n + 1);
    sort(c + 1, c + n + 1);
    int ptr1 = 1, ptr2 = 1;
    for(int i = 1;i<=n;i++){
        if(v[i]) continue;
        ++ans;
        for(int j = 1;j<=n;j++){
            if((a[i].first - a[i].second >= a[j].first - a[j].second && a[j].second <= a[i].second) || (a[i].first + a[i].second >= a[j].first + a[j].second && a[i].second <= a[j].second)) v[j] = 1;
        }
    }
    cout << ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...