Submission #1262536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262536		phtung	Lightning Rod (NOI18_lightningrod)	C++20	0 / 100	1107 ms	330692 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct Interval {
    int L, R, id;
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<pair<int,int>> b(n);
    for (int i=0;i<n;i++) cin >> b[i].first >> b[i].second;

    vector<Interval> seg;
    for (int i=0;i<n;i++) {
        int x = b[i].first, y = b[i].second;
        seg.push_back({x-y, x+y, i});
    }

    sort(seg.begin(), seg.end(), [&](auto a, auto b){
        if (a.L != b.L) return a.L < b.L;
        return a.R > b.R;
    });

    // lọc khoảng bị bao trùm
    vector<Interval> clean;
    int bestR = -1e18;
    for (auto it: seg) {
        if (it.R > bestR) {
            clean.push_back(it);
            bestR = it.R;
        }
    }

    // greedy phủ các tòa
    int res = 0;
    int coverR = -1e18;
    int idx = 0;
    for (int i=0;i<n;i++) {
        int x = b[i].first, y = b[i].second;
        // điểm phải nằm trong ít nhất một khoảng
        if (x > coverR) {
            // chọn khoảng trong clean có L <= x và R lớn nhất
            while (idx+1 < (int)clean.size() && clean[idx+1].L <= x) idx++;
            coverR = clean[idx].R;
            res++;
        }
    }
    cout << res << "\n";
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 26
• Subtask 6: 0 / 10
• Subtask 7: 0 / 20