Submission #1123780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123780		LucaIlie	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	358 ms	6284 KiB

Main

#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";
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31