Submission #1171882

#TimeUsernameProblemLanguageResultExecution timeMemory
1171882lancethedragontrainerLightning Rod (NOI18_lightningrod)C++20
66 / 100
1099 ms156232 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
 
typedef long long ll;
 
struct Building {
    ll A; // X - Y
    ll B; // X + Y
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<Building> buildings(n);
    for (int i = 0; i < n; i++){
        ll X, Y;
        cin >> X >> Y;
        buildings[i].A = X - Y;
        buildings[i].B = X + Y;
    }
    // Sort by B descending. For equal B, sort by A ascending.
    sort(buildings.begin(), buildings.end(), [](const Building &a, const Building &b) {
        if(a.B == b.B) return a.A < b.A;
        return a.B > b.B;
    });
 
    ll bestA = LLONG_MAX; // best (smallest) A among chosen rods
    int ans = 0;
    for(auto &b : buildings){
        // A building is covered by some rod if some chosen rod's A <= its A.
        if(bestA <= b.A)
            continue;
        // Otherwise, plant a rod here and update bestA.
        ans++;
        bestA = b.A;
    }
 
    cout << ans << "\n";
    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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...