oj.uz

Submission #146973

# Submission time Handle Problem Language Result Execution time Memory
146973 2019-08-27T01:57:46 Z gs14004 Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 640 ms 246844 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 10000005;

static char buf[1 << 19]; // size : any number geq than 1024
static int idx = 0;
static int bytes = 0;
static inline int _read() {
	if (!bytes || idx == bytes) {
		bytes = (int)fread(buf, sizeof(buf[0]), sizeof(buf), stdin);
		idx = 0;
	}
	return buf[idx++];
}
static inline int _readInt() {
	int x = 0, s = 1;
	int c = _read();
	while (c <= 32) c = _read();
	if (c == '-') s = -1, c = _read();
	while (c > 32) x = 10 * x + (c - '0'), c = _read();
	if (s < 0) x = -x;
	return x;
}


int n;
pi a[MAXN];
vector<int> stk;

bool in(int x, int y){
	return a[x].first - a[x].second <= a[y].first - a[y].second &&
	a[y].first + a[y].second <= a[x].first + a[x].second;
}

int main(){
	n = _readInt();
	for(int i=0; i<n; i++){
		a[i].first = _readInt();
		a[i].second = _readInt();
		if(stk.empty()) stk.push_back(i);
		else{
			if(in(stk.back(), i)) continue;
			while(!stk.empty() && in(i, stk.back())) stk.pop_back();
			stk.push_back(i);
		}
	}
	printf("%d\n", sz(stk));
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 132476 KB Output is correct
2 Correct 520 ms 230088 KB Output is correct
3 Correct 509 ms 230296 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 256 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 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 256 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 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 256 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 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 256 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 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 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 15 ms 2296 KB Output is correct
15 Correct 15 ms 2296 KB Output is correct
16 Correct 15 ms 2800 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 112676 KB Output is correct
2 Correct 496 ms 199320 KB Output is correct
3 Correct 479 ms 194708 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 132476 KB Output is correct
2 Correct 520 ms 230088 KB Output is correct
3 Correct 509 ms 230296 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 256 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 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 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 15 ms 2296 KB Output is correct
18 Correct 15 ms 2296 KB Output is correct
19 Correct 15 ms 2800 KB Output is correct
20 Correct 476 ms 112676 KB Output is correct
21 Correct 496 ms 199320 KB Output is correct
22 Correct 479 ms 194708 KB Output is correct
23 Correct 640 ms 246844 KB Output is correct
24 Correct 609 ms 228268 KB Output is correct
25 Correct 592 ms 211036 KB Output is correct