Submission #146999

#TimeUsernameProblemLanguageResultExecution timeMemory
146999jun6873Lightning Rod (NOI18_lightningrod)C++11
80 / 100
2064 ms193400 KiB
#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, b[maxn];
pint a[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() {
    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 a[b[k-1]].y <= a[i].y) k--;
        if (!k or a[b[k-1]].x < a[i].x) b[k++] = i;
    }

    cout << k << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...