oj.uz

Submission #227648

# Submission time Handle Problem Language Result Execution time Memory
227648 2020-04-28T08:59:31 Z Autoratch Lightning Rod (NOI18_lightningrod) C++14
100 / 100
 672 ms 191912 KB 
#include <bits/stdc++.h>
using namespace std;

int n,x,y;
stack<pair<int,int> > a;

int readInt()
{
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}

int main()
{
    n = readInt();
    for(int i = 0;i < n;i++)
    {
        x = readInt(),y = readInt();
        while(!a.empty() and abs(a.top().first-x)<=y-a.top().second) a.pop();
        if(a.empty() or abs(a.top().first-x)>a.top().second-y) a.push({x,y});
    }
    printf("%d",(int)a.size());
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 82248 KB Output is correct
2 Correct 442 ms 191912 KB Output is correct
3 Correct 437 ms 186744 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 17 ms 1408 KB Output is correct
15 Correct 17 ms 1408 KB Output is correct
16 Correct 16 ms 2176 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 51576 KB Output is correct
2 Correct 430 ms 147580 KB Output is correct
3 Correct 411 ms 143772 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 82248 KB Output is correct
2 Correct 442 ms 191912 KB Output is correct
3 Correct 437 ms 186744 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 17 ms 1408 KB Output is correct
18 Correct 17 ms 1408 KB Output is correct
19 Correct 16 ms 2176 KB Output is correct
20 Correct 377 ms 51576 KB Output is correct
21 Correct 430 ms 147580 KB Output is correct
22 Correct 411 ms 143772 KB Output is correct
23 Correct 672 ms 175328 KB Output is correct
24 Correct 602 ms 156512 KB Output is correct
25 Correct 569 ms 139916 KB Output is correct