제출 #915664

#제출 시각아이디문제언어결과실행 시간메모리
915664berrAdvertisement 2 (JOI23_ho_t2)C++17
100 / 100
193 ms33628 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 1e9+7;



signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;

    vector<array<int, 2>> a(n);

    for(auto &[x, y]: a) cin >> x >> y;

    sort(a.begin(), a.end());
    vector<array<int, 3>> ar(n);
    for(int i=0; i<n; i++){
        ar[i] = {a[i][1], i, a[i][0]};
    }

    sort(ar.begin(), ar.end());
    reverse(ar.begin(), ar.end());
    
    vector<int> vis(n);
    int ans = 0;

    for(auto [x, y, z]: ar){
        if(vis[y]) continue;

        int l = y-1, r = y+1;
        ans++;
        while(r<n &&!vis[r] && abs(a[r][0]-z) <= x-a[r][1]){
            vis[r] = 1;
            r++;
        }

        while(l>=0 &&!vis[l] && abs(a[l][0]-z) <= x-a[l][1]){
            vis[l] = 1;
            l--;
        }
    }

    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...