답안 #520028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520028	2022-01-28T07:33:13 Z	sumit_kk10	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	912 ms	262144 KB

lightningrod

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define ll long long
#define F first 
#define S second
using namespace std;
const int N = 1e7 + 5, MOD = 1e9 + 7;

inline int readInt() {
    int x = 0;
    char ch = getchar();
    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;
}

void solve(){
	int n = readInt();
	pair<int, int> a[n];
	for(int i = 0; i < n; ++i){
		a[i].F = readInt();
		a[i].S = readInt();
	}
	sort(a, a + n);
	int pre_max[n], suf_mn[n + 1];
	pre_max[0] = a[0].F + a[0].S;
	for(int i = 1; i < n; ++i)
	    pre_max[i] = max(pre_max[i - 1], a[i].F + a[i].S);
	suf_mn[n - 1] = a[n - 1].F - a[n - 1].S;
	for(int i = n - 2; i >= 0; --i)
	    suf_mn[i] = min(suf_mn[i + 1], a[i].F - a[i].S);
	int ans = (suf_mn[1] > (a[0].F - a[0].S));
	suf_mn[n] = INT_MAX;
	for(int i = 1; i < n; ++i){
	    if((pre_max[i - 1] >= (a[i].F + a[i].S)) or (suf_mn[i + 1] <= (a[i].F - a[i].S))) 
	        continue;
	    ++ans;
	}
	cout << ans << '\n';
}
 
int main(){
	fast;
	int t = 1;
	// cin >> t;
	while(t--)
		solve();
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	670 ms	177072 KB	Output is correct
2	Correct	688 ms	167600 KB	Output is correct
3	Correct	641 ms	162788 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	312 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	324 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	312 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	324 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct

Subtask #4

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	312 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	324 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct

Subtask #5

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	312 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	324 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	19 ms	6712 KB	Output is correct
15	Correct	20 ms	6652 KB	Output is correct
16	Correct	17 ms	5808 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	654 ms	175920 KB	Output is correct
2	Correct	698 ms	252308 KB	Output is correct
3	Correct	671 ms	246320 KB	Output is correct

Subtask #7

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	670 ms	177072 KB	Output is correct
2	Correct	688 ms	167600 KB	Output is correct
3	Correct	641 ms	162788 KB	Output is correct
4	Correct	0 ms	312 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	316 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	19 ms	6712 KB	Output is correct
18	Correct	20 ms	6652 KB	Output is correct
19	Correct	17 ms	5808 KB	Output is correct
20	Correct	654 ms	175920 KB	Output is correct
21	Correct	698 ms	252308 KB	Output is correct
22	Correct	671 ms	246320 KB	Output is correct
23	Correct	912 ms	262144 KB	Output is correct
24	Correct	875 ms	262144 KB	Output is correct
25	Correct	847 ms	262144 KB	Output is correct