Submission #1356160

#TimeUsernameProblemLanguageResultExecution timeMemory
1356160nathlol2Advertisement 2 (JOI23_ho_t2)C++20
10 / 100
113 ms17888 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;
        while(ptr1 <= n && get<0>(b[ptr1]) <= a[i].first - a[i].second){
            if(get<1>(b[ptr1]) <= a[i].second) v[get<2>(b[ptr1])] = 1;
            ++ptr1;
        }
        while(ptr2 <= n && get<0>(c[ptr2]) <= a[i].first + a[i].second){
            if(get<1>(c[ptr2]) >= a[i].second) v[get<2>(c[ptr2])] = 1;
            ++ptr2;
        }
    }
    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...