Submission #200046

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
200046	2020-02-05T04:02:18 Z	wilwxk	Lightning Rod (NOI18_lightningrod)	C++14	100 / 100	1719 ms	78424 KB

lightningrod

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

const int MAXN = 1e7+7;
pair<int, int> v[MAXN];
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();
		v[i].first = a+b;
		v[i].second = b-a;
	}
	sort(v+1, v+1+n);
 
	int ans = 0; int mx = -(2e9+7);
	for(int i = n; i >= 1; i--) if(v[i].second > mx) mx = v[i].second, ans++;
 
	printf("%d\n", ans);
}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	610 ms	76280 KB	Output is correct
2	Correct	631 ms	75896 KB	Output is correct
3	Correct	588 ms	74104 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	376 KB	Output is correct
4	Correct	6 ms	256 KB	Output is correct
5	Correct	5 ms	256 KB	Output is correct
6	Correct	5 ms	256 KB	Output is correct
7	Correct	4 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	376 KB	Output is correct
4	Correct	6 ms	256 KB	Output is correct
5	Correct	5 ms	256 KB	Output is correct
6	Correct	5 ms	256 KB	Output is correct
7	Correct	4 ms	256 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	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	376 KB	Output is correct
4	Correct	6 ms	256 KB	Output is correct
5	Correct	5 ms	256 KB	Output is correct
6	Correct	5 ms	256 KB	Output is correct
7	Correct	4 ms	256 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	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	376 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	376 KB	Output is correct
4	Correct	6 ms	256 KB	Output is correct
5	Correct	5 ms	256 KB	Output is correct
6	Correct	5 ms	256 KB	Output is correct
7	Correct	4 ms	256 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	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	376 KB	Output is correct
14	Correct	34 ms	1784 KB	Output is correct
15	Correct	29 ms	1912 KB	Output is correct
16	Correct	21 ms	1784 KB	Output is correct

Subtask #6

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	653 ms	78424 KB	Output is correct
2	Correct	660 ms	78332 KB	Output is correct
3	Correct	634 ms	76280 KB	Output is correct

Subtask #7

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	610 ms	76280 KB	Output is correct
2	Correct	631 ms	75896 KB	Output is correct
3	Correct	588 ms	74104 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	6 ms	256 KB	Output is correct
8	Correct	5 ms	256 KB	Output is correct
9	Correct	5 ms	256 KB	Output is correct
10	Correct	4 ms	256 KB	Output is correct
11	Correct	5 ms	256 KB	Output is correct
12	Correct	4 ms	256 KB	Output is correct
13	Correct	5 ms	256 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	5 ms	376 KB	Output is correct
17	Correct	34 ms	1784 KB	Output is correct
18	Correct	29 ms	1912 KB	Output is correct
19	Correct	21 ms	1784 KB	Output is correct
20	Correct	653 ms	78424 KB	Output is correct
21	Correct	660 ms	78332 KB	Output is correct
22	Correct	634 ms	76280 KB	Output is correct
23	Correct	1719 ms	71392 KB	Output is correct
24	Correct	1412 ms	71344 KB	Output is correct
25	Correct	1052 ms	72056 KB	Output is correct