Submission #787909

#	Time	Username	Problem	Language	Result	Execution time	Memory
787909		guagua0407	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	235 ms	34644 KiB

Main

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

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