Submission #955604

#	Time	Username	Problem	Language	Result	Execution time	Memory
955604		Kakarot	Advertisement 2 (JOI23_ho_t2)	C++98	59 / 100	2084 ms	9632 KiB

Main

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

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