Submission #146998

#	Time	Username	Problem	Language	Result	Execution time	Memory
146998		jun6873	Lightning Rod (NOI18_lightningrod)	C++11	76 / 100	1830 ms	262148 KiB

Main

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

using lint = long long;
using pint = pair<lint, lint>;
#define x first
#define y second

const int maxn = 10000004;
int n, k;
pint a[maxn], b[maxn];

//https://www.geeksforgeeks.org/fast-io-for-competitive-programming/
void fastscan(int &number)
{
    //variable to indicate sign of input number
    bool negative = false;
    register int c;
 
    number = 0;
 
    // extract current character from buffer
    c = getchar();
    if (c=='-')
    {
        // number is negative
        negative = true;
 
        // extract the next character from the buffer
        c = getchar();
    }
 
    // Keep on extracting characters if they are integers
    // i.e ASCII Value lies from '0'(48) to '9' (57)
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
 
    // if scanned input has a negative sign, negate the
    // value of the input number
    if (negative)
        number *= -1;
}

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

    fastscan(n);
    for (int i=0; i<n; i++) {
        int x, y;
        fastscan(x); fastscan(y);
        a[i] = pint(x+y, y-x);
    }

    for (int i=0; i<n; i++) {
        while (k and b[k-1].y <= a[i].y) k--;
        if (!k or b[k-1].x < a[i].x) b[k++] = a[i];
    }

    cout << k << '\n';
}

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