CSES - BAPC 2017

CSES - BAPC 2017 - Results

Submission details
Task:	Manhattan Mornings
Sender:	Antti Röyskö
Submission time:	2017-10-24 18:16:09 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.05 s	details
#2	ACCEPTED	0.04 s	details
#3	ACCEPTED	0.04 s	details
#4	ACCEPTED	0.04 s	details
#5	ACCEPTED	0.06 s	details
#6	ACCEPTED	0.03 s	details
#7	ACCEPTED	0.04 s	details
#8	ACCEPTED	0.04 s	details
#9	ACCEPTED	0.05 s	details
#10	ACCEPTED	0.04 s	details
#11	ACCEPTED	0.04 s	details
#12	ACCEPTED	0.04 s	details
#13	ACCEPTED	0.04 s	details
#14	ACCEPTED	0.04 s	details
#15	ACCEPTED	0.05 s	details
#16	ACCEPTED	0.04 s	details
#17	ACCEPTED	0.06 s	details
#18	ACCEPTED	0.04 s	details
#19	ACCEPTED	0.12 s	details
#20	ACCEPTED	0.05 s	details
#21	ACCEPTED	0.09 s	details
#22	ACCEPTED	0.09 s	details
#23	ACCEPTED	0.08 s	details
#24	ACCEPTED	0.09 s	details
#25	ACCEPTED	0.08 s	details
#26	ACCEPTED	0.04 s	details
#27	ACCEPTED	0.05 s	details
#28	ACCEPTED	0.14 s	details
#29	ACCEPTED	0.12 s	details
#30	ACCEPTED	0.10 s	details
#31	ACCEPTED	0.12 s	details
#32	ACCEPTED	0.04 s	details
#33	ACCEPTED	0.04 s	details
#34	ACCEPTED	0.09 s	details
#35	ACCEPTED	0.11 s	details
#36	ACCEPTED	0.12 s	details
#37	ACCEPTED	0.09 s	details
#38	ACCEPTED	0.07 s	details
#39	ACCEPTED	0.10 s	details
#40	ACCEPTED	0.12 s	details
#41	ACCEPTED	0.08 s	details
#42	ACCEPTED	0.07 s	details
#43	ACCEPTED	0.08 s	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:38:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < places.size(); ++i) {
                                  ^

Code

#include <iostream>
#include <set>
#include <utility>
#include <vector>
#include <algorithm>

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	
	int n;
	std::cin >> n;

	int sx, sy, wx, wy;
	std::cin >> sx >> sy >> wx >> wy;
	if (sx > wx) {
		int temp = sx;
		sx = wx;
		wx = temp;
		temp = sy;
		sy = wy;
		wy = temp;
	}
	int dir = 1;
	if (wy < sy) {
		dir = -1;
	}

	std::vector<std::pair<int, int>> places;
	for (int i = 0; i < n; ++i) {
		int x, y;
		std::cin >> x >> y;
		places.push_back({x, dir * y});
	}
	std::sort(places.begin(), places.end());
	std::set<std::pair<int, int>> best;
	best.insert({dir * sy,0});
	for (int i = 0; i < places.size(); ++i) {
		int x = places[i].first;
		int y = places[i].second * dir;
		if (x < sx) continue;
		if (x > wx) break;
		auto point = best.upper_bound({dir * y, n});
		if (point == best.begin()) {
			continue;
		} else {
			--point;
			int val = 1 + point->second;
			while(true) {
				point = best.upper_bound({dir * y, val});
				if (point == best.end()) break;
				if (point->second <= val) {
					best.erase(point);
				} else {
					break;
				}
			}
			best.insert({dir * y, val});
		}
	}
	/*
	for (auto at : best) {
		std::cout << at.first << ' ' << at.second << '\n';
	}
	*/
	auto point = best.upper_bound({dir * wy, n});
	if (point == best.begin()) {
		std::cout << "0\n";
	} else {
		--point;
		std::cout << point->second << '\n';
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
`10001 100 10100 10100 100 100 100 101 101 102 102 ...` view save

correct output
`1` view save

user output
`1` view save

Test 2

Verdict: ACCEPTED

input
`51 100 80 50 130 50 80 51 81 52 82 ...` view save

correct output
`1` view save

user output
`1` view save

Test 3

Verdict: ACCEPTED

input
`100 100 100 200 200 151 190 102 196 120 198 ...` view save

correct output
`15` view save

user output
`15` view save

Test 4

Verdict: ACCEPTED

input
`100 100 100 200 200 107 116 106 198 110 110 ...` view save

correct output
`17` view save

user output
`17` view save

Test 5

Verdict: ACCEPTED

input
`10001 100 100 10100 10100 100 100 101 101 102 102 ...` view save

correct output
`10001` view save

user output
`10001` view save

Test 6

Verdict: ACCEPTED

input
`51 0 80 50 130 0 80 1 81 2 82 ...` view save

correct output
`51` view save

user output
`51` view save

Test 7

Verdict: ACCEPTED

input
`50 10 10 20 10 21 9 13 9 15 11 ...` view save

correct output
`16` view save

user output
`16` view save

Test 8

Verdict: ACCEPTED

input
`50 10 10 10 20 11 13 10 16 11 12 ...` view save

correct output
`18` view save

user output
`18` view save

Test 9

Verdict: ACCEPTED

input
`1000 20 20 60 60 59 42 34 21 35 41 ...` view save

correct output
`72` view save

user output
`72` view save

Test 10

Verdict: ACCEPTED

input
`1000 60 20 20 60 59 42 34 21 35 41 ...` view save

correct output
`70` view save

user output
`70` view save

Test 11

Verdict: ACCEPTED

input
`50 10 20 10 10 11 13 10 16 11 12 ...` view save

correct output
`18` view save

user output
`18` view save

Test 12

Verdict: ACCEPTED

input
`1000 20 60 60 20 59 42 34 21 35 41 ...` view save

correct output
`70` view save

user output
`70` view save

Test 13

Verdict: ACCEPTED

input
`1000 60 60 20 20 59 42 34 21 35 41 ...` view save

correct output
`72` view save

user output
`72` view save

Test 14

Verdict: ACCEPTED

input
`50 20 10 10 10 21 9 13 9 15 11 ...` view save

correct output
`16` view save

user output
`16` view save

Test 15

Verdict: ACCEPTED

input
`100 100 100 200 200 92 116 99 198 95 110 ...` view save

correct output
`0` view save

user output
`0` view save

Test 16

Verdict: ACCEPTED

input
`100 100 100 200 200 203 116 210 198 206 110 ...` view save

correct output
`0` view save

user output
`0` view save

Test 17

Verdict: ACCEPTED

input
`100 100 100 200 200 151 90 102 91 120 98 ...` view save

correct output
`0` view save

user output
`0` view save

Test 18

Verdict: ACCEPTED

input
`100 100 100 200 200 151 201 102 202 120 209 ...` view save

correct output
`0` view save

user output
`0` view save

Test 19

Verdict: ACCEPTED

input
`99856 0 0 315 315 0 0 0 1 0 2 ...` view save

correct output
`631` view save

user output
`631` view save

Test 20

Verdict: ACCEPTED

input
`121 30 30 40 40 30 30 30 31 30 32 ...` view save

correct output
`21` view save

user output
`21` view save

Test 21

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 81777 81727 7139 7165 18678 18626 ...` view save

correct output
`2000` view save

user output
`2000` view save

Test 22

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 42065 47939 60860 69144 24315 25689 ...` view save

correct output
`20` view save

user output
`20` view save

Test 23

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 24711 24693 27493 27511 58083 58121 ...` view save

correct output
`1000` view save

user output
`1000` view save

Test 24

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 93337 93167 10108 10396 28728 28776 ...` view save

correct output
`400` view save

user output
`400` view save

Test 25

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 299880 999700120 999535510 464490 999907060 92940 ...` view save

correct output
`4` view save

user output
`4` view save

Test 26

Verdict: ACCEPTED

input
`100 100 100 200 200 157 200 117 200 142 200 ...` view save

correct output
`100` view save

user output
`100` view save

Test 27

Verdict: ACCEPTED

input
`100 100 100 200 200 130 173 130 131 130 118 ...` view save

correct output
`100` view save

user output
`100` view save

Test 28

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 897804452 627427519 606065659 628843521 477686514 492734427 ...` view save

correct output
`622` view save

user output
`622` view save

Test 29

Verdict: ACCEPTED

input
`100000 0 0 100000 100000 95475 11246 59599 37233 71739 19501 ...` view save

correct output
`615` view save

user output
`615` view save

Test 30

Verdict: ACCEPTED

input
`100000 0 0 300 300 13 285 52 40 158 178 ...` view save

correct output
`1233` view save

user output
`1233` view save

Test 31

Verdict: ACCEPTED

input
`100000 0 0 10 10 6 4 1 9 8 9 ...` view save

correct output
`17669` view save

user output
`17669` view save

Test 32

Verdict: ACCEPTED

input
`10 0 0 10 10 6 4 1 9 8 9 ...` view save

correct output
`5` view save

user output
`5` view save

Test 33

Verdict: ACCEPTED

input
`1000 1234 76543 1265 76224 1545 76719 1199 76306 1305 76185 ...` view save

correct output
`2` view save

user output
`2` view save

Test 34

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 999998482 1518 999999380 620 52008 999947992 ...` view save

correct output
`2001` view save

user output
`2001` view save

Test 35

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 999960616 39384 39185 999960815 45237 999954763 ...` view save

correct output
`201` view save

user output
`201` view save

Test 36

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 999989308 10692 999998647 1353 44068 999955932 ...` view save

correct output
`21` view save

user output
`21` view save

Test 37

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 999955327 44673 999932388 67612 11879 999988121 ...` view save

correct output
`1001` view save

user output
`1001` view save

Test 38

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 0 0 1000000000 1000000000 1 999999999 ...` view save

correct output
`101` view save

user output
`101` view save

Test 39

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 62791 999937209 98083 999901917 999902435 97565 ...` view save

correct output
`801` view save

user output
`801` view save

Test 40

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 43604 999956396 80721 999919279 999958750 999958750 ...` view save

correct output
`4001` view save

user output
`4001` view save

Test 41

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 99142 999900858 60558 999939442 44046 999955954 ...` view save

correct output
`401` view save

user output
`401` view save

Test 42

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 56902 999943098 7395 999992605 76388 999923612 ...` view save

correct output
`41` view save

user output
`41` view save

Test 43

Verdict: ACCEPTED

input
`100000 0 0 1000000000 1000000000 11427 999988573 23698 999976302 57515 999942485 ...` view save

correct output
`5` view save

user output
`5` view save

BAPC 2017

Manhattan Mornings

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Tasks

Submissions (Antti Röyskö)