oj.uz

Submission #141080

# Submission time Handle Problem Language Result Execution time Memory
141080 2019-08-06T15:29:11 Z tincamatei Lightning Rod (NOI18_lightningrod) C++14
100 / 100
 639 ms 188208 KB 
#include <bits/stdc++.h>

const int BUFF = 1 << 12;
const int MAX_N = 10000000;

int cursor = BUFF - 1;
char buff[BUFF];

char getChar(FILE *fin) {
	cursor++;
	if(cursor == BUFF) {
		cursor = 0;
		fread(buff, 1, BUFF, fin);
	}
	return buff[cursor];
}

int getnr(FILE *fin) {
	char ch = getChar(fin);
	while(!isdigit(ch))
		ch = fgetc(fin);
	int nr = 0;
	while(isdigit(ch)) {
		nr = nr * 10 + ch - '0';
		ch = getChar(fin);
	}
	return nr;
}

struct Point {
	int x, y;
} v[MAX_N];

int main() {
	int N, x, y;
	Point pnt;

	N = getnr(stdin);
	int top = 0;
	for(int i = 0; i < N; ++i) {
		x = getnr(stdin);
		y = getnr(stdin);

		pnt = {x - y, x + y};
		
		while(top > 0 && pnt.x <= v[top - 1].x && pnt.y >= v[top - 1].y)
			--top;
		if(top == 0 || (top > 0 && !(v[top - 1].x <= pnt.x && v[top - 1].y >= pnt.y)))
			v[top++] = pnt;
	}

	printf("%d", top);

	return 0;
}

Compilation message

lightningrod.cpp: In function 'char getChar(FILE*)':
lightningrod.cpp:13:8: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fread(buff, 1, BUFF, fin);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 150548 KB Output is correct
2 Correct 474 ms 188208 KB Output is correct
3 Correct 465 ms 183196 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 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 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 504 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 256 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 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 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 15 ms 3832 KB Output is correct
15 Correct 15 ms 3704 KB Output is correct
16 Correct 15 ms 3704 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 124040 KB Output is correct
2 Correct 462 ms 145236 KB Output is correct
3 Correct 446 ms 141708 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 150548 KB Output is correct
2 Correct 474 ms 188208 KB Output is correct
3 Correct 465 ms 183196 KB Output is correct
4 Correct 2 ms 256 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 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 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 15 ms 3832 KB Output is correct
18 Correct 15 ms 3704 KB Output is correct
19 Correct 15 ms 3704 KB Output is correct
20 Correct 450 ms 124040 KB Output is correct
21 Correct 462 ms 145236 KB Output is correct
22 Correct 446 ms 141708 KB Output is correct
23 Correct 639 ms 138064 KB Output is correct
24 Correct 596 ms 156672 KB Output is correct
25 Correct 599 ms 139740 KB Output is correct