제출 #955604

#제출 시각아이디문제언어결과실행 시간메모리
955604KakarotAdvertisement 2 (JOI23_ho_t2)C++98
59 / 100
2084 ms9632 KiB
#include <bits/stdc++.h>
#define int int64_t
using namespace std;

void setIO() {
    cin.tie(0)->sync_with_stdio(0);
}

bool pred(pair<int, int> &src, pair<int, int> &dest) {
    return (abs(src.first - dest.first) <= src.second - dest.second);
}

void mark(int idx, vector<bool> &marked, vector<pair<int, int>> &points) {
    if(marked[idx]) return;
    marked[idx] = true;
    for(int i = 0; i < idx; i++) {
        if(marked[i] or !pred(points[idx], points[i])) continue;
        mark(i, marked, points);
    }
}

void solve() {
    //cout << "zco";
    int n;
    cin >> n;
    vector<pair<int, int>> points(n);
    map<int, int> f;
    bool flag = true;
    for(auto &x : points) {
        cin >> x.first >> x.second;
        f[x.first]++;
    }
    for(int i = 1; i < n; i++) {
        if(points[i].second != points[i-1].second) flag = false;
    }
    sort(points.begin(), points.end(), [](pair<int, int> &a, pair<int, int> &b) { return a.second < b.second; });
    int ans = 0;
    vector<bool> marked(n, false);
    for(int i = n-1; i > -1; i--) {
        if(marked[i]) continue;
        mark(i, marked, points);
        ans++;
    }    
    cout << (flag ? f.size() : ans);
}

int32_t main() {
    setIO();
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...