Submission #1171881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171881		lancethedragontrainer	Lightning Rod (NOI18_lightningrod)	C++20	21 / 100	963 ms	156376 KiB

Main

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

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