CSES - APIO 2012

CSES - APIO 2012 - Results

Submission details
Task:	Guard
Sender:	Olli
Submission time:	2019-03-16 19:08:32 +0200
Language:	C++
Status:	READY
Result:	50

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	40
#3	TIME LIMIT EXCEEDED	0

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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < ba.size(); ++i) {
                  ~~^~~~~~~~~~~
input/code.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < bet.size(); ++i) {
                 ~~^~~~~~~~~~~~
input/code.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < go.size(); ++i) {
                 ~~^~~~~~~~~~~
input/code.cpp:105:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ans.size(); ++i) {
                  ~~^~~~~~~~~~~~
input/code.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < go.size(); ++i) {
                 ~~^~~~~~~~~~~
input/code.cpp:131:20: warning: comparison between signed and u...

Code

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

using namespace std;

const int N = 1e5 + 5;


typedef pair<int, int> pii;

vector<pii> go;
vector<pii> ba;

int t[N];

vector<int> ev[N];

unordered_map<int, int> ma;

int main() {
	int n, k, m;
	cin >> n >> k >> m;
	for(int i = 1; i <= m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		if(c == 1) {
			go.push_back({a, b});
		} else {
			ba.push_back({a, b});
		}
	}
	sort(ba.begin(), ba.end());


	vector<pii> bet;
	if(ba.size() > 0) {
		int be = ba[0].first;
		int en = ba[0].second;

		for(int i = 1; i < ba.size(); ++i) {
			int a = ba[i].first;
			int b = ba[i].second;
			if(a > be + 1) {
				bet.push_back({be, en});
				be = a;
				en = b;
			} else {
				en = max(en, b);
			}
		}
		bet.push_back({be, en});
	}
	for(int i = 1; i <= n; ++i) {
		t[i] = 1;
	}

	for(int i = 0; i < bet.size(); ++i) {
		int a = bet[i].first;
		int b = bet[i].second;
		for(int j = a; j <= b; ++j) {
			t[j] = 0;
		}
	}


	int ind = 1;
	for(int i = 1; i <= n; ++i) {
		ma[i] = 0;
	}
	for(int i = 1; i <= n; ++i) {
		if(t[i] == 0) {
			ma[i] = ind;
			continue;
		}
		ma[i] = ind;
		++ind;
	}

	for(int i = 0; i < go.size(); ++i) {
		go[i] = {ma[go[i].first], go[i].second};
	}


	ind = 0;
	for(int i = 1; i <= n; ++i) {
		if(t[i] == 0) {
			ma[i] = ind;
			continue;
		}
		++ind;
		ma[i] = ind;
	}
	if(ind == k) {
		vector<int> ans;
		int cur = 0;
		for(int i = 1; i <= n; ++i) {
			if(ma[i] != cur) {
				++cur;
				ans.push_back(i);
			}
		}
		for(int i = 0; i < ans.size(); ++i) {
			cout << ans[i] << "\n";
		}
		return 0;
	}

	for(int i = 0; i < go.size(); ++i) {
		go[i] = {go[i].first, ma[go[i].second]};
		ev[go[i].first].push_back(i+1);
		ev[go[i].second].push_back(-(i+1));
	}

	for(int i = 1; i <= n; ++i) {
		sort(ev[i].begin(), ev[i].end());
		reverse(ev[i].begin(), ev[i].end());
	}

	vector<int> ans;
	int cur = 0;
	for(int ii = 1; ii <= n; ++ii) {
		int i = ma[ii];
		if(i == cur) continue;
		++cur;
		t[i] = 0;
		bool ok = true;
		int en = ev[i].size() - 1;
		for(int j = 0; j < ev[i].size(); ++j) {
			int s = ev[i][j];
			if(s < 0) break;
			if(s == -ev[i][en]) {
				ok = false;
				break;
			}
			if(s > -ev[i][en]) {
				continue;
			}
			while(s < -ev[i][en]) {
				--en;
			}
			if(s == -ev[i][en]) {
				ok = false;
				break;
			}
		}
		if(!ok) {
			ans.push_back(ii);
			continue;
		}
		set<int> active;

		int nee = 0;
		for(int j = 0; j <= n; ++j) {
			for(auto a : ev[j]) {
				if(a > 0) {
					active.insert(a);
				} else {
					set<int>::iterator it = active.find(-a);
					if(it != active.end()) {
						++nee;
						active.clear();
					}
				}
			}
			if(j == i-1) {
				bool del = false;
				for(auto a : ev[i]) {
					if(a < 0) {
						set<int>::iterator it = active.find(-a);
						if(it != active.end()) {
							del = true;
							break;
						}
					}
				}
			
				if(del) {
					++nee;
					active.clear();
				}
				for(auto a : ev[i]) {
					if(a > 0) {
						active.insert(a);
					}
				}
				++j;
			}
		}
		if(nee > k) ans.push_back(ii);
		t[i] = 1;
	}

	if(ans.size() == 0) {
		cout << -1 << "\n";
	} else {
		for(auto i : ans) {
			cout << i << "\n";
		}
	}
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 9 100 1 9 1 11 12 1 3 19 1 10 20 1 ...` view save

correct output
`-1` view save

user output
`-1` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 12 20 12 14 1 16 19 1 6 18 1 1 9 1 ...` view save

correct output
`1 2 3 6 7 ...` view save

user output
`1 2 3 6 7 ...` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 6 100 14 18 1 17 19 1 3 16 1 17 19 1 ...` view save

correct output
`3 14 15 16 18 ...` view save

user output
`3 14 15 16 18 ...` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 6 100 7 15 1 8 8 1 1 3 1 4 11 1 ...` view save

correct output
`8 9 14 16 19` view save

user output
`8 9 14 16 19` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 7 100 17 18 1 4 4 1 2 7 1 10 18 1 ...` view save

correct output
`1 2 4 6 8 ...` view save

user output
`1 2 4 6 8 ...` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 6 100 7 16 1 2 12 1 20 20 1 6 9 1 ...` view save

correct output
`2 11 15 18 20` view save

user output
`2 11 15 18 20` view save

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 8 100 5 18 1 14 20 1 18 18 1 1 13 1 ...` view save

correct output
`1 4 13 14 18` view save

user output
`1 4 13 14 18` view save

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 1 2 1 9 0 11 20 0` view save

correct output
`10` view save

user output
`10` view save

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
`20 20 1 7 12 1` view save

correct output
`1 2 3 4 5 ...` view save

user output
`1 2 3 4 5 ...` view save

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1 1 1 1 1 1` view save

correct output
`1` view save

user output
`1` view save

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
`1000 604 1000 375 674 1 514 875 1 728 728 0 10 10 0 ...` view save

correct output
`1 3 6 7 8 ...` view save

user output
`1 3 6 7 8 ...` Truncated

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
`1000 183 1000 521 531 1 245 255 1 455 460 1 200 468 1 ...` view save

correct output
`19 22 33 57 77 ...` view save

user output
`19 22 33 57 77 ...` Truncated

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
`1000 361 1000 584 695 1 446 997 1 569 570 1 59 60 1 ...` view save

correct output
`2 4 6 8 15 ...` view save

user output
`2 4 6 8 15 ...` Truncated

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
`1000 12 1000 543 543 0 63 420 1 340 340 0 288 288 0 ...` view save

correct output
`57 385` view save

user output
`57 385` view save

Test 15

Group: 2, 3

Verdict: ACCEPTED

input
`1000 29 1000 740 952 1 602 606 1 660 660 0 472 472 0 ...` view save

correct output
`774 783` view save

user output
`774 783` view save

Test 16

Group: 2, 3

Verdict: ACCEPTED

input
`1000 612 1000 253 993 1 498 842 1 191 191 0 958 958 0 ...` view save

correct output
`1 3 4 5 8 ...` view save

user output
`1 3 4 5 8 ...` Truncated

Test 17

Group: 2, 3

Verdict: ACCEPTED

input
`1000 192 1000 542 547 1 647 648 1 530 530 1 60 163 1 ...` view save

correct output
`4 11 13 24 27 ...` view save

user output
`4 11 13 24 27 ...` Truncated

Test 18

Group: 2, 3

Verdict: ACCEPTED

input
`1000 367 1000 21 919 1 204 999 1 492 493 1 38 39 1 ...` view save

correct output
`2 4 6 8 10 ...` view save

user output
`2 4 6 8 10 ...` Truncated

Test 19

Group: 2, 3

Verdict: ACCEPTED

input
`1000 9 1000 543 543 0 78 217 1 340 340 0 288 288 0 ...` view save

correct output
`120 257 555 904` view save

user output
`120 257 555 904` view save

Test 20

Group: 2, 3

Verdict: ACCEPTED

input
`1000 28 1000 455 954 1 279 370 1 407 407 0 235 235 0 ...` view save

correct output
`179 411 510 944` view save

user output
`179 411 510 944` view save

Test 21

Group: 2, 3

Verdict: ACCEPTED

input
`1000 25 1000 673 901 1 333 924 1 878 878 0 335 335 0 ...` view save

correct output
`-1` view save

user output
`-1` view save

Test 22

Group: 2, 3

Verdict: ACCEPTED

input
`1000 183 1000 451 452 1 406 417 1 880 883 1 123 259 1 ...` view save

correct output
`2 11 15 16 23 ...` view save

user output
`2 11 15 16 23 ...` Truncated

Test 23

Group: 2, 3

Verdict: ACCEPTED

input
`1000 368 1000 142 917 1 73 808 1 528 529 1 37 38 1 ...` view save

correct output
`2 4 6 8 13 ...` view save

user output
`2 4 6 8 13 ...` Truncated

Test 24

Group: 2, 3

Verdict: ACCEPTED

input
`1000 9 1000 543 543 0 202 706 1 340 340 0 288 288 0 ...` view save

correct output
`119` view save

user output
`119` view save

Test 25

Group: 2, 3

Verdict: ACCEPTED

input
`1000 30 1000 457 501 1 159 217 1 823 823 0 978 978 0 ...` view save

correct output
`562` view save

user output
`562` view save

Test 26

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 259 100000 70265 94761 1 512 62132 1 32170 32170 0 45057 45057 0 ...` view save

correct output
`-1` view save

user output
(empty)

Test 27

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 310 100000 36712 95986 1 6774 6774 0 41262 41262 0 42735 51183 1 ...` view save

correct output
`55314 65758` view save

user output
(empty)

Test 28

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 308 100000 4723 17721 1 28590 28590 0 90553 90553 0 58222 69710 1 ...` view save

correct output
`18048 45778 55102 79641` view save

user output
(empty)

Test 29

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 9281 100000 2146 2148 1 95934 95936 1 23741 79333 0 22669 76745 0 ...` view save

correct output
`3 14 18 24 53 ...` view save

user output
(empty)

Test 30

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 18849 100000 97331 97332 1 6924 6932 1 55268 55277 1 3984 3985 1 ...` view save

correct output
`1 10 12 16 20 ...` view save

user output
(empty)

Test 31

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 36955 100000 51007 51012 1 63071 63072 1 9317 61009 1 75457 75458 1 ...` view save

correct output
`2 4 9 11 13 ...` view save

user output
(empty)

Test 32

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 2134 100000 37393 37393 0 66060 66060 0 29148 29319 1 59637 59637 0 ...` view save

correct output
`777 796 815 1156 1250 ...` view save

user output
(empty)

Test 33

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 295 100000 74178 80289 1 78374 78374 0 73504 73504 0 63584 74642 1 ...` view save

correct output
`52739 89458 89969` view save

user output
(empty)

Test 34

Group: 3

Verdict: ACCEPTED

input
`100000 20058 100000 13468 89073 0 12536 89053 0 95907 95910 1 14252 85912 0 ...` view save

correct output
`1 2 3 4 5 ...` view save

user output
`1 2 3 4 5 ...` Truncated

Test 35

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 18802 100000 94192 94199 1 73216 73222 1 31268 31276 1 35786 35790 1 ...` view save

correct output
`20 47 53 84 96 ...` view save

user output
(empty)

Test 36

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 37072 100000 51058 51059 1 63164 63165 1 15990 75136 1 75367 75368 1 ...` view save

correct output
`6 8 10 12 14 ...` view save

user output
(empty)

Test 37

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 2123 100000 37393 37393 0 66060 66060 0 75929 75961 1 59637 59637 0 ...` view save

correct output
`538 835 1295 1766 1884 ...` view save

user output
(empty)

Test 38

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 297 100000 37623 88595 1 63978 63978 0 24490 24490 0 64997 74211 1 ...` view save

correct output
`11217 45656 48264 59100` view save

user output
(empty)

Test 39

Group: 3

Verdict: ACCEPTED

input
`100000 26782 100000 17681 86590 0 18919 85356 0 11236 11238 1 17421 80681 0 ...` view save

correct output
`1 2 3 4 5 ...` view save

user output
`1 2 3 4 5 ...` Truncated

Test 40

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 18695 100000 39276 39281 1 99842 99852 1 71530 71533 1 85154 85159 1 ...` view save

correct output
`1 8 35 41 53 ...` view save

user output
(empty)

Test 41

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 37091 100000 50717 50718 1 62957 62958 1 17480 66007 1 75147 75148 1 ...` view save

correct output
`2 4 6 8 21 ...` view save

user output
(empty)

Test 42

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 2145 100000 37393 37393 0 66060 66060 0 58103 58121 1 59637 59637 0 ...` view save

correct output
`8 48 369 797 1010 ...` view save

user output
(empty)

Test 43

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 299 100000 41538 81745 1 9875 9875 0 1099 1099 0 32939 82591 1 ...` view save

correct output
`23460 28661` view save

user output
(empty)

APIO 2012

Guard

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 (Olli)