Submission #1322490

#TimeUsernameProblemLanguageResultExecution timeMemory
1322490cubedAdvertisement 2 (JOI23_ho_t2)C++20
100 / 100
123 ms16084 KiB
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define f first
// #define s second
#define pb(x) push_back(x)
#define int long long


/*
ORDERED SET PDBS

#include <bits/extc++.h>
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

const int MOD = 1e9+7;
const int inf = 1e9;
const int INF = 1e18+20;
const int LOG = 25;

/*
n<=1000


*/
int n;

vector<pair<int, int>> a;

vector<pair<int, int>> given;

int ans = inf;

/*void f (int i) {
    if (i==n) {
        int reached=0;
        vector<int> tt(n, 0);

        for (auto x:given) {
            for (int i=0;i<n; i++) {
                if (abs(x.first - a[i].first) <= x.second - a[i].second && !tt[i]) {
                    reached++;
                    tt[i]=1;
                }
            }
        }

        if (reached==n) {
            ans=min(ans, cnt);
        }

        return;
    }

    // donate the book to this guy
    given.push_back(a[i]);
    cnt++;
    f(i+1);
    given.pop_back();
    cnt--;

    // do not donate the book to this guy
    f(i+1);
}*/

bool comp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first != b.first) return a.first < b.first;
    return a.second > b.second;
}

void solve() {
    cin>>n;

    a.resize(n);
    vector<pair<int, int>> maxi(n);
    for (int i=0; i<n; i++) {
        int x, e;
        cin>>x>>e;
        a[i] = {x-e, x+e};
    }

    sort(a.begin(), a.end(), comp);

    int cnt=0;
    int maxr = -INF;

    for (auto i:a) {
        if (i.second > maxr) {
            cnt++;
            maxr=i.second;
        }
    }

    cout<<cnt<<endl;

    

}

bool multi=false;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);


    int t=1;
    if (multi) cin>>t;
 
    while (t--) solve();
 
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...