Submission #1297208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297208		chaitanyamehta	Lightning Rod (NOI18_lightningrod)	C++20	0 / 100	1032 ms	234408 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static ll A[10000005];
static ll C[10000005];
static ll suffA[10000005];

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

    int N;
    cin >> N;

    for (int i = 0; i < N; i++) {
        ll X, Y;
        cin >> X >> Y;
        A[i] = X + Y;     // For right coverage
        C[i] = Y - X;     // For left coverage
    }

    // Build suffix max of A
    suffA[N-1] = A[N-1];
    for (int i = N-2; i >= 0; i--) {
        suffA[i] = max(A[i], suffA[i+1]);
    }

    ll rods = 0;
    ll prefMaxC = LLONG_MIN; // max of C[0..i-1]

    for (int i = 0; i < N; i++) {
        bool leftCover  = (i > 0 && prefMaxC >= C[i]);
        bool rightCover = (i < N-1 && suffA[i+1] >= A[i]);
        if (!leftCover && !rightCover)
            rods++;

        prefMaxC = max(prefMaxC, C[i]);
    }

    cout << rods << "\n";
    return 0;
}

• 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