Submission #1064456

#TimeUsernameProblemLanguageResultExecution timeMemory
1064456Dennis_JasonAdvertisement 2 (JOI23_ho_t2)C++14
10 / 100
310 ms17972 KiB
#include <bitset>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#define int long long
#define pb push_back
#define MOD 1000000007
#define NMAX 250001
#define nl '\n'
#define INF 1000000007
#define pii1 pair<int, pair<int,int>>  (1,(1,2));
#define pii pair<int,int>
#define tpl tuple<int,int,int>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");
/*
    --------------------DEMONSTRATION---------------------


    ------------------------END--------------------------

 */
int n;
vector<pii>v;
signed main() {

    cin>>n;
    v.resize(n+1);
    for(int i=1;i<=n;++i)
    {
        cin>>v[i].first>>v[i].second;
    }
    auto cmp=[&](pii a,pii b)
    {
        if(a.first==b.first)
            return a.second<b.second;

        return a.first>b.first;
    };
    sort(v.begin()+1,v.end(),cmp);
//    for(int i=1;i<=n;++i)
//    {
//        cout<<v[i].first<<" "<<v[i].second<<nl;
//    }
    int i=1;
    int ans=0;
    while(i<=n)
    {
        int st=i+1;
        int dr=n;
        int ind=i;
        while(st<=dr)
        {
            int mid=(st+dr)/2;
            if(abs(v[i].first-v[mid].first)<=v[i].second-v[mid].second)
            {
                ind=mid;
                st=mid+1;
            }
            else
                dr=mid-1;
        }
        i=ind+1;
        ans++;
    }
    cout<<ans<<nl;
    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...