Submission #1281504

#TimeUsernameProblemLanguageResultExecution timeMemory
1281504nanaseyuzukiAdvertisement 2 (JOI23_ho_t2)C++20
69 / 100
2092 ms24132 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
const int mn=5e5+5;
vector<pii>a;
int n;
void sub1(){
    unordered_set<int>s;
    for(int i=0;i<n;i++){
        s.insert(a[i].fi);
    }
    cout<<s.size();
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    a.resize(n);
    bool task1=true;
    for(int i=0;i<n;i++) cin>>a[i].fi>>a[i].se;
    for(int i=1;i<n;i++){
        if(a[i].se!=a[i-1].se) task1=false;
    }
    if(task1&&n>=10000){
        sub1();
    }
    else{
        sort(a.begin(),a.end(),[](const pii&p1,const pii&p2){
            if(p1.se==p2.se)
                return p1.fi<p2.fi;
            return p1.se>p2.se;
        });
        vector<pii>cc;
        for(int i=0;i<n;i++){
            int x=a[i].fi;
            int e=a[i].se;
            bool check=false;
            for(int j=0;j<(int)cc.size();j++){
                int dx=abs(x-cc[j].fi);
                int de=cc[j].se-e;
                if(dx<=de){
                    check=true;
                    break;
                }
            }
            if(!check) cc.push_back(a[i]);
        }
        cout<<cc.size();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...