답안 #123108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
123108	2019-06-30T08:48:33 Z	mechfrog88	Lightning Rod (NOI18_lightningrod)	C++14	80 / 100	2000 ms	124412 KB

lightningrod

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;	

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	n = readInt();
	int arrx[n];
	int arry[n];
	for (int z=0;z<n;z++){
		arrx[z] = readInt();
		arry[z] = readInt();
	}
	stack <int> s;
	for (int z=0;z<n;z++){
		int a = arrx[z]-arry[z];
		int b = arrx[z]+arry[z];
		if (s.empty()){
			s.push(z);
		}
		int c = arrx[s.top()]-arry[s.top()];
		int d = arrx[s.top()]+arry[s.top()];
		if (c <= a && b <= d) continue;
		else{
			while (a <= c && d <= b){
				s.pop();
				if (s.size() == 0) break;
				c = arrx[s.top()]-arry[s.top()];
				d = arrx[s.top()]+arry[s.top()];
			}
			s.push(z);
		}
	}
	printf("%d",int(s.size()));
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1763 ms	124412 KB	Output is correct
2	Correct	1764 ms	120984 KB	Output is correct
3	Correct	1697 ms	118868 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 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	376 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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 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	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	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct

Subtask #5

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 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	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	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	56 ms	5360 KB	Output is correct
15	Correct	53 ms	5240 KB	Output is correct
16	Correct	48 ms	4912 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1598 ms	111740 KB	Output is correct
2	Correct	1554 ms	109428 KB	Output is correct
3	Correct	1524 ms	109560 KB	Output is correct

Subtask #7

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1763 ms	124412 KB	Output is correct
2	Correct	1764 ms	120984 KB	Output is correct
3	Correct	1697 ms	118868 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	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	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	56 ms	5360 KB	Output is correct
18	Correct	53 ms	5240 KB	Output is correct
19	Correct	48 ms	4912 KB	Output is correct
20	Correct	1598 ms	111740 KB	Output is correct
21	Correct	1554 ms	109428 KB	Output is correct
22	Correct	1524 ms	109560 KB	Output is correct
23	Execution timed out	2067 ms	62472 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-