Submission #200045

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
200045	2020-02-05T04:00:45 Z	wilwxk	Lightning Rod (NOI18_lightningrod)	C++14	100 / 100	850 ms	229716 KB

lightningrod

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

vector<pair<int, int> > st;
int n;

int getn() {
	char ch = getchar_unlocked();
    int ans = 0;
    while(!isdigit(ch)) {
        ch = getchar_unlocked();
    }
    while(isdigit(ch)) {
        ans = ans * 10 + ch - '0';
        ch = getchar_unlocked();
    }
    return ans;
}

int main() {
	n = getn();
	for(int i = 1; i <= n; i++) {
		int a = getn();
		int b = getn();
		if(st.size() && a-st.back().first <= abs(b-st.back().second) && st.back().second >= b) continue; 
		while(st.size() && a-st.back().first <= abs(b-st.back().second)) st.pop_back();
		st.push_back({a, b});
	}
	printf("%d\n", int(st.size()));
}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	500 ms	131924 KB	Output is correct
2	Correct	627 ms	229588 KB	Output is correct
3	Correct	631 ms	229716 KB	Output is correct

Subtask #2

7.0 / 7.0

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

Subtask #3

12.0 / 12.0

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

Subtask #4

21.0 / 21.0

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

Subtask #5

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 ms	296 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	256 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	256 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	256 KB	Output is correct
11	Correct	5 ms	256 KB	Output is correct
12	Correct	5 ms	256 KB	Output is correct
13	Correct	5 ms	380 KB	Output is correct
14	Correct	19 ms	376 KB	Output is correct
15	Correct	17 ms	376 KB	Output is correct
16	Correct	18 ms	1520 KB	Output is correct

Subtask #6

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	488 ms	66176 KB	Output is correct
2	Correct	537 ms	145472 KB	Output is correct
3	Correct	545 ms	142152 KB	Output is correct

Subtask #7

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	500 ms	131924 KB	Output is correct
2	Correct	627 ms	229588 KB	Output is correct
3	Correct	631 ms	229716 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	256 KB	Output is correct
6	Correct	5 ms	296 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	256 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	256 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	256 KB	Output is correct
14	Correct	5 ms	256 KB	Output is correct
15	Correct	5 ms	256 KB	Output is correct
16	Correct	5 ms	380 KB	Output is correct
17	Correct	19 ms	376 KB	Output is correct
18	Correct	17 ms	376 KB	Output is correct
19	Correct	18 ms	1520 KB	Output is correct
20	Correct	488 ms	66176 KB	Output is correct
21	Correct	537 ms	145472 KB	Output is correct
22	Correct	545 ms	142152 KB	Output is correct
23	Correct	850 ms	175916 KB	Output is correct
24	Correct	747 ms	157048 KB	Output is correct
25	Correct	685 ms	140384 KB	Output is correct