Submission #1297192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297192		chaitanyamehta	Lightning Rod (NOI18_lightningrod)	C++20	0 / 100	1077 ms	234320 KiB

Main

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

int main() {
    int N;
    if (scanf("%d", &N) != 1) return 0;

    vector<ll> A(N), B(N);

    for (int i = 0; i < N; ++i) {
        ll X, Y;
        scanf("%lld %lld", &X, &Y);
        A[i] = X + Y;   // used for right coverage
        B[i] = Y - X;   // used for left coverage
    }

    // suffix max of A
    vector<ll> suffA(N);
    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 prefMinB = LLONG_MAX; // min of B[0..i-1]

    for (int i = 0; i < N; ++i) {
        bool coveredLeft  = (i > 0 && prefMinB <= B[i]);      // some j < i with B[j] <= B[i]
        bool coveredRight = (i + 1 < N && suffA[i+1] >= A[i]); // some j > i with A[j] >= A[i]
        if (!coveredLeft && !coveredRight) ++rods;
        prefMinB = min(prefMinB, B[i]);
    }

    printf("%lld\n", rods);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%lld %lld", &X, &Y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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