제출 #1297194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1297194		chaitanyamehta	Lightning Rod (NOI18_lightningrod)	C++20	0 / 100	253 ms	235180 KiB

Main

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

static const int BUFSIZE = 1 << 20;
static char buf[BUFSIZE];
static int bufpos = 0, buflen = 0;
static inline char nextChar() {
    if (bufpos >= buflen) {
        buflen = (int)fread(buf, 1, BUFSIZE, stdin);
        bufpos = 0;
        if (buflen == 0) return 0;
    }
    return buf[bufpos++];
}
static inline bool readUnsignedLongLong(unsigned long long &out) {
    char c; out = 0;
    do { c = nextChar(); if (!c) return false; } while (c <= ' ');
    while (c > ' ') {
        out = out * 10 + (c - '0');
        c = nextChar();
        if (!c) break;
    }
    return true;
}

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

    unsigned long long Nu;
    if (!readUnsignedLongLong(Nu)) return 0;
    size_t N = (size_t)Nu;

    // allocate arrays for A and B
    // A = X + Y (use int64)
    // B = Y - X (use int64)
    int64 *A = (int64*)malloc(sizeof(int64) * N);
    int64 *B = (int64*)malloc(sizeof(int64) * N);
    if (!A || !B) {
        fprintf(stderr, "Allocation failed\n");
        return 0;
    }

    for (size_t i = 0; i < N; ++i) {
        unsigned long long Xu, Yu;
        readUnsignedLongLong(Xu);
        readUnsignedLongLong(Yu);
        int64 X = (int64)Xu;
        int64 Y = (int64)Yu;
        A[i] = X + Y;         // 0 .. 2e9 fits in 64-bit
        B[i] = Y - X;         // -1e9 .. 1e9 fits in 64-bit
    }

    // compute suffix maximum of A
    int64 *suffA = (int64*)malloc(sizeof(int64) * N);
    if (!suffA) {
        fprintf(stderr, "Allocation failed\n");
        return 0;
    }
    suffA[N-1] = A[N-1];
    for (int i = (int)N - 2; i >= 0; --i) {
        suffA[i] = max(A[i], suffA[i+1]);
    }

    long long rods = 0;
    int64 prefMinB = LLONG_MAX; // min of B[0..i-1]

    for (size_t i = 0; i < N; ++i) {
        bool coveredLeft = (i > 0 && prefMinB <= B[i]);      // exists j < i with B[j] <= B[i]
        bool coveredRight = (i + 1 < N && suffA[i+1] >= A[i]); // exists j > i with A[j] >= A[i]
        if (!coveredLeft && !coveredRight) ++rods;
        // update prefix min for next indices
        if (B[i] < prefMinB) prefMinB = B[i];
    }

    printf("%lld\n", rods);

    free(A);
    free(B);
    free(suffA);
    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