Submission #787909

#TimeUsernameProblemLanguageResultExecution timeMemory
787909guagua0407Advertisement 2 (JOI23_ho_t2)C++17
100 / 100
235 ms34644 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()

struct DSU{
    vector<int> e;
    DSU(int n){
        e=vector<int>(n,-1);
    }
    int find(int x){
        return (e[x]<0?x:e[x]=find(e[x]));
    }
    void unite(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b) return;
        if(e[a]>e[b]) swap(a,b);
        e[a]+=e[b];
        e[b]=a;
    }
};

bool comp(pair<int,int> a,pair<int,int> b){
    if(a.s!=b.s) return a.s<b.s;
    return a.f<b.f;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    vector<pair<int,int>> num(n);
    for(int i=0;i<n;i++){
        int x,e;
        cin>>x>>e;
        num[i]={x,e};
    }
    sort(all(num),comp);
    multiset<pair<int,int>> vec;
    int ans=0;
    for(int i=n-1;i>=0;i--){
        auto it=vec.lower_bound({num[i].s-num[i].f,0});
        if(it==vec.end()){
            vec.insert({num[i].s-num[i].f,i});
            ans++;
        }
        else{
            auto id=(*it).s;
            if(abs(num[id].f-num[i].f)>(num[id].s-num[i].s)){
                vec.insert({num[i].s-num[i].f,i});
                ans++;
            }
        }
    }
    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...