oj.uz

Submission #146999

# Submission time Handle Problem Language Result Execution time Memory
146999 2019-08-27T03:50:34 Z jun6873 Lightning Rod (NOI18_lightningrod) C++11
80 / 100
 2000 ms 193400 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() {
    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';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1771 ms 190032 KB Output is correct
2 Correct 1767 ms 193400 KB Output is correct
3 Correct 1718 ms 188152 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 348 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 2 ms 376 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 348 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 2 ms 376 KB Output is correct
8 Correct 2 ms 256 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 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 348 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 2 ms 376 KB Output is correct
8 Correct 2 ms 256 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 380 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 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 348 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 2 ms 376 KB Output is correct
8 Correct 2 ms 256 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 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 56 ms 3320 KB Output is correct
15 Correct 53 ms 3344 KB Output is correct
16 Correct 47 ms 3448 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1628 ms 180820 KB Output is correct
2 Correct 1603 ms 180600 KB Output is correct
3 Correct 1562 ms 176376 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1771 ms 190032 KB Output is correct
2 Correct 1767 ms 193400 KB Output is correct
3 Correct 1718 ms 188152 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 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 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 56 ms 3320 KB Output is correct
18 Correct 53 ms 3344 KB Output is correct
19 Correct 47 ms 3448 KB Output is correct
20 Correct 1628 ms 180820 KB Output is correct
21 Correct 1603 ms 180600 KB Output is correct
22 Correct 1562 ms 176376 KB Output is correct
23 Execution timed out 2064 ms 119164 KB Time limit exceeded
24 Halted 0 ms 0 KB -