제출 #1171881

#제출 시각아이디문제언어결과실행 시간메모리
1171881lancethedragontrainerLightning Rod (NOI18_lightningrod)C++20
21 / 100
963 ms156376 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Fast I/O setup
static auto __ = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

typedef long long ll;

int main() {
    int n;
    cin >> n;
    
    vector<pair<ll, ll>> buildings(n);
    for (int i = 0; i < n; i++) {
        cin >> buildings[i].first >> buildings[i].second;
    }
    
    // The key insight: we want to place rods on buildings that protect the greatest range to the right
    // We process buildings from left to right and place a rod when necessary
    
    int rod_count = 0;
    int i = 0;
    
    while (i < n) {
        // Place a new rod
        rod_count++;
        
        // Find the building that extends protection the furthest to the right
        ll max_protection = -1;
        
        // j is the candidate building for placing the rod
        int j = i;
        while (j < n && buildings[j].first - buildings[i].first <= buildings[j].second - buildings[i].second) {
            // Calculate how far right this rod can protect:
            // x + y represents the maximum x-coordinate that can be protected
            // (if we go further right, the height difference would exceed the x difference)
            ll protection_reach = buildings[j].first + buildings[j].second;
            
            if (protection_reach > max_protection) {
                max_protection = protection_reach;
            }
            
            j++;
        }
        
        // Skip all buildings that are protected by this rod
        while (i < n && buildings[i].first <= max_protection - buildings[i].second) {
            i++;
        }
    }
    
    cout << rod_count << endl;
    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...