oj.uz

Submission #146996

# Submission time Handle Problem Language Result Execution time Memory
146996 2019-08-27T03:42:00 Z jun6873 Lightning Rod (NOI18_lightningrod) C++11
66 / 100
 2000 ms 183868 KB 
#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() {
    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);
    }

    sort(a, a+n);
    reverse(a, a+n);
    n = unique(a, a+n, [](pint x, pint y) { return x.x == y.x; }) - a;
    reverse(a, a+n);

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

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 152188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 75 ms 3236 KB Output is correct
15 Correct 69 ms 3320 KB Output is correct
16 Correct 53 ms 3576 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1998 ms 180648 KB Output is correct
2 Execution timed out 2007 ms 183868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 152188 KB Time limit exceeded
2 Halted 0 ms 0 KB -