Submission #919720

#	Time	Username	Problem	Language	Result	Execution time	Memory
919720		AnasAAF	Advertisement 2 (JOI23_ho_t2)	C++14	69 / 100	2021 ms	52004 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define float double

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    vector<pair<ll, ll>>v(n);
    vector<pair<ll, pair<ll, ll>>>vp(n);
    set<int>st, st2;
    for(int i=0;i<n;i++){
        ll a, b;cin>>a>>b;
        v[i] = {a, b};
        vp[i] = {b, {a, i}};
        st.insert(a);
        st2.insert(b);
    }
    if(st2.size()==1){
        cout<<st.size()<<endl;
        return 0;
    }
    sort(vp.rbegin(), vp.rend());
    vector<int>vis(n+1);
    int ans(0);
    queue<int>q;
    for(int i=0;i<n;i++){
        int a = vp[i].second.first, b = vp[i].first, ind = vp[i].second.second;
        if(!vis[ind]){
            ans++;
            q.push(ind);
        }
        while(!q.empty()){
            int in = q.front();
            int x = v[in].first, y=v[in].second;
            q.pop();
            for(int j=0;j<n;j++){
                if(vis[j])continue;
                int m = v[j].first, n=v[j].second;
                if(abs(x-m)<=y-n){
                    q.push(j);
                    vis[j]=1;
                }
            }
        }
    }
    cout<<min(ans, (int)st.size())<<endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:13: warning: unused variable 'a' [-Wunused-variable]
   29 |         int a = vp[i].second.first, b = vp[i].first, ind = vp[i].second.second;
      |             ^
Main.cpp:29:37: warning: unused variable 'b' [-Wunused-variable]
   29 |         int a = vp[i].second.first, b = vp[i].first, ind = vp[i].second.second;
      |                                     ^

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