Submission #998551

#	Time	Username	Problem	Language	Result	Execution time	Memory
998551		faqinyeager	Advertisement 2 (JOI23_ho_t2)	C++17	69 / 100	2057 ms	57536 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N;
vector<ll> x, e;

int main(){
    cin >> N;
    
    x.resize(N), e.resize(N);
    
    map<ll, ll> tmp;
    
    for(int i = 0; i < N; i++) cin >> x[i] >> e[i];
        
    for(int i = 0; i < N; i++){
        tmp[x[i]] = max(tmp[x[i]], e[i]);
    }
    
    if(*min_element(e.begin(), e.end()) == *max_element(e.begin(), e.end())){
        cout << tmp.size();
        return 0;
    }

    
    int sz = tmp.size(), ans = 0;
    
    vector<bool> used(sz, 0);
    
    vector<pair<ll, ll>> pos;
    for(auto [x, y]: tmp){
        pos.push_back({y, x});
    }
    
    sort(pos.rbegin(), pos.rend());
    
    for(int i = 0; i < sz; i++){
        if(used[i] == 1) continue;
        ans++;
        for(int j = i + 1; j < sz; j++){
            if(used[j] == 1) continue;
            ll xi = abs(pos[i].second - pos[j].second);
            ll ei = pos[i].first - pos[j].first;
            if(ei >= xi) used[j] = 1;
        }
    }
    cout << ans;
    
}

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