제출 #1123780

#제출 시각아이디문제언어결과실행 시간메모리
1123780LucaIlieAdvertisement 2 (JOI23_ho_t2)C++20
100 / 100
358 ms6284 KiB
#include <bits/stdc++.h>

using namespace std;

struct resident {
    int x, e, canBeRoot;
};

const int MAX_N = 5e5;
const int INF = 1e9 + 1;
resident r[MAX_N + 1];

int main() {
    int n;

    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> r[i].x >> r[i].e;
        r[i].canBeRoot = true;
    }

    sort( r + 1, r + 1 + n, []( resident a, resident b ) {
        if ( a.x == b.x )
            return a.e > b.e;
        return a.x < b.x;
    } );
    int maxLeft = -INF;
    for ( int i = 1; i <= n; i++ ) {
        if ( r[i].x + r[i].e > maxLeft )
            maxLeft = r[i].x + r[i].e;
        else
            r[i].canBeRoot = false;
    }
    sort( r + 1, r + 1 + n, []( resident a, resident b ) {
        if ( a.x == b.x ) {
            if ( a.e == b.e )
                return a.canBeRoot < b.canBeRoot;
            return a.e < b.e;
        }
        return a.x < b.x;
    } );
    int minRight = INF;
    for ( int i = n; i >= 1; i-- ) {
        if ( r[i].x - r[i].e < minRight )
            minRight = r[i].x - r[i].e;
        else
            r[i].canBeRoot = false;
    }

    int ans = 0;
    for ( int i = 1; i <= n; i++ )
        ans += r[i].canBeRoot;

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