답안 #430570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
430570	2021-06-16T16:06:31 Z	nvmdava	식물 비교 (IOI20_plants)	C++17	100 / 100	1460 ms	56688 KB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
int n;

struct Segtree{
	pair<int, int> mn[800005];
	int lz[800005];
	void push(int id, int l, int r){
		mn[id].ff += lz[id];
		if(l != r){
			lz[id << 1] += lz[id];
			lz[id << 1 | 1] += lz[id];
		}
		lz[id] = 0;
	}

	void build(int id, int l, int r, vector<int>& v){
		if(l == r){
			mn[id] = {v[l], l};
			return;
		}
		int m = (l + r) >> 1;
		build(id << 1, l, m, v);
		build(id << 1 | 1, m + 1, r, v);

		mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
	}

	void update(int id, int l, int r, int L, int R, int x){
		if(L <= l && r <= R){
			lz[id] += x;
			push(id, l, r);
			return;
		}
		push(id, l, r);
		if(l > R || r < L) return;
		int m = (l + r) >> 1;
		update(id << 1, l, m, L, R, x);
		update(id << 1 | 1, m + 1, r, L, R, x);
		mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
	}

	pair<int, int> query(int id, int l, int r, int L, int R){
		push(id, l, r);
		if(l > R || r < L)
			return {1'000'000, 1};
		if(L <= l && r <= R)
			return mn[id];
		int m = (l + r) >> 1;
		return min(query(id << 1, l, m, L, R), query(id << 1 | 1, m + 1, r, L, R));
	}
} s, t;

int le[200005][20], ri[200005][20];
vector<int> q;
int h[200005];

bool cw(int x, int y, int z){
	if(x <= y && y <= z)
		return 1;
	if(y <= z && z <= x)
		return 1;
	if(z <= x && x <= y)
		return 1;
	return 0;
}

int k;

void init(int k, std::vector<int> v) {
	n = v.size();
	--k;
	::k = k;
	for(auto& x : v)
		x = k - x;
	s.build(1, 0, n - 1, v);
	
	for(auto& x : v)
		x = 0;
	t.build(1, 0, n - 1, v);
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < 20; ++j)
			ri[i][j] = le[i][j] = -1;
	for(int i = 1; i <= n; ++i){
		int now;
		if(q.empty())
			now = s.query(1, 0, n - 1, 0, n - 1).ss;
		else {
			now = q.back();
			q.pop_back();
		}

		pair<int, int> tmp = min(s.query(1, 0, n - 1, now - k, now - 1), s.query(1, 0, n - 1, now - k + n, n - 1));
		
		while(tmp.ff == 0){
			q.push_back(now);
			now = tmp.ss;
			tmp = min(s.query(1, 0, n - 1, now - k, now - 1), s.query(1, 0, n - 1, now - k + n, n - 1));
		}
		
		s.update(1, 0, n - 1, now, now, 800'005);
		s.update(1, 0, n - 1, now - k, now - 1, -1);
		s.update(1, 0, n - 1, now - k + n, n - 1, -1);
		
		h[now] = i;
		
		tmp = min(t.query(1, 0, n - 1, now - k, now - 1), t.query(1, 0, n - 1, now - k + n, n - 1));
		le[now][0] = tmp.ff == 0 ? -1 : tmp.ss;

		tmp = min(t.query(1, 0, n - 1, now + 1, now + k), t.query(1, 0, n - 1, 0, now + k - n));
		ri[now][0] = tmp.ff == 0 ? -1 : tmp.ss;
		for(int i = 0; le[now][i] != -1; ++i){
			le[now][i + 1] = le[le[now][i]][i];
			if(le[now][i + 1] != -1 && cw(le[now][i], le[now][i + 1], now))
				le[now][i + 1] = -1;
		}

		for(int i = 0; ri[now][i] != -1; ++i){
			ri[now][i + 1] = ri[ri[now][i]][i];
			if(ri[now][i + 1] != -1 && cw(now, ri[now][i + 1], ri[now][i]))
				ri[now][i + 1] = -1;
		}
		
		t.update(1, 0, n - 1, now, now, -i);
	}

}

int compare_plants(int x, int y){
	if(h[x] > h[y]) return -compare_plants(y, x);
	int ry = y, ly = y;

	for(int i = 19; i >= 0; --i)
		if(ri[ry][i] != -1 && cw(ry, ri[ry][i], x) && x != ry)
			ry = ri[ry][i];

	if(min(abs(ry - x), n - abs(ry - x)) <= k && h[ry] >= h[x])
		return -1;

	for(int i = 19; i >= 0; --i)
		if(le[ly][i] != -1 && cw(x, le[ly][i], ly) && x != ly)
			ly = le[ly][i];

	if(min(abs(ly - x), n - abs(ly - x)) <= k && h[ly] >= h[x])
		return -1;

	return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	12748 KB	Output is correct
2	Correct	9 ms	12748 KB	Output is correct
3	Correct	8 ms	12748 KB	Output is correct
4	Correct	6 ms	12736 KB	Output is correct
5	Correct	6 ms	12748 KB	Output is correct
6	Correct	75 ms	15588 KB	Output is correct
7	Correct	142 ms	19508 KB	Output is correct
8	Correct	656 ms	52860 KB	Output is correct
9	Correct	686 ms	52876 KB	Output is correct
10	Correct	647 ms	52864 KB	Output is correct
11	Correct	732 ms	53052 KB	Output is correct
12	Correct	752 ms	53288 KB	Output is correct
13	Correct	808 ms	53040 KB	Output is correct
14	Correct	800 ms	52952 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	12748 KB	Output is correct
2	Correct	8 ms	12748 KB	Output is correct
3	Correct	7 ms	12836 KB	Output is correct
4	Correct	7 ms	12748 KB	Output is correct
5	Correct	8 ms	12876 KB	Output is correct
6	Correct	13 ms	13096 KB	Output is correct
7	Correct	94 ms	16632 KB	Output is correct
8	Correct	9 ms	12876 KB	Output is correct
9	Correct	12 ms	13088 KB	Output is correct
10	Correct	106 ms	16556 KB	Output is correct
11	Correct	115 ms	16452 KB	Output is correct
12	Correct	106 ms	16756 KB	Output is correct
13	Correct	99 ms	16636 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	12748 KB	Output is correct
2	Correct	8 ms	12748 KB	Output is correct
3	Correct	7 ms	12836 KB	Output is correct
4	Correct	7 ms	12748 KB	Output is correct
5	Correct	8 ms	12876 KB	Output is correct
6	Correct	13 ms	13096 KB	Output is correct
7	Correct	94 ms	16632 KB	Output is correct
8	Correct	9 ms	12876 KB	Output is correct
9	Correct	12 ms	13088 KB	Output is correct
10	Correct	106 ms	16556 KB	Output is correct
11	Correct	115 ms	16452 KB	Output is correct
12	Correct	106 ms	16756 KB	Output is correct
13	Correct	99 ms	16636 KB	Output is correct
14	Correct	169 ms	19468 KB	Output is correct
15	Correct	1335 ms	52944 KB	Output is correct
16	Correct	162 ms	19460 KB	Output is correct
17	Correct	1396 ms	52936 KB	Output is correct
18	Correct	1111 ms	52828 KB	Output is correct
19	Correct	979 ms	52816 KB	Output is correct
20	Correct	1187 ms	53060 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	12748 KB	Output is correct
2	Correct	7 ms	12748 KB	Output is correct
3	Correct	104 ms	15968 KB	Output is correct
4	Correct	1047 ms	53164 KB	Output is correct
5	Correct	994 ms	52984 KB	Output is correct
6	Correct	1339 ms	56228 KB	Output is correct
7	Correct	1394 ms	56384 KB	Output is correct
8	Correct	1412 ms	56620 KB	Output is correct
9	Correct	942 ms	55904 KB	Output is correct
10	Correct	953 ms	55972 KB	Output is correct
11	Correct	763 ms	55780 KB	Output is correct
12	Correct	919 ms	55996 KB	Output is correct
13	Correct	1016 ms	56172 KB	Output is correct

Subtask #5
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	12748 KB	Output is correct
2	Correct	8 ms	12820 KB	Output is correct
3	Correct	10 ms	12876 KB	Output is correct
4	Correct	8 ms	12748 KB	Output is correct
5	Correct	8 ms	12748 KB	Output is correct
6	Correct	10 ms	12876 KB	Output is correct
7	Correct	28 ms	13444 KB	Output is correct
8	Correct	24 ms	13448 KB	Output is correct
9	Correct	27 ms	13764 KB	Output is correct
10	Correct	25 ms	13756 KB	Output is correct
11	Correct	25 ms	13804 KB	Output is correct
12	Correct	27 ms	13760 KB	Output is correct
13	Correct	24 ms	13776 KB	Output is correct

Subtask #6
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	12748 KB	Output is correct
2	Correct	8 ms	12748 KB	Output is correct
3	Correct	8 ms	12748 KB	Output is correct
4	Correct	7 ms	12748 KB	Output is correct
5	Correct	10 ms	13004 KB	Output is correct
6	Correct	860 ms	52844 KB	Output is correct
7	Correct	1284 ms	52940 KB	Output is correct
8	Correct	1352 ms	52944 KB	Output is correct
9	Correct	1327 ms	52948 KB	Output is correct
10	Correct	886 ms	52932 KB	Output is correct
11	Correct	1333 ms	53024 KB	Output is correct
12	Correct	857 ms	53168 KB	Output is correct
13	Correct	942 ms	52956 KB	Output is correct
14	Correct	1219 ms	55352 KB	Output is correct
15	Correct	1363 ms	55620 KB	Output is correct
16	Correct	872 ms	54984 KB	Output is correct
17	Correct	845 ms	55196 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	12748 KB	Output is correct
2	Correct	9 ms	12748 KB	Output is correct
3	Correct	8 ms	12748 KB	Output is correct
4	Correct	6 ms	12736 KB	Output is correct
5	Correct	6 ms	12748 KB	Output is correct
6	Correct	75 ms	15588 KB	Output is correct
7	Correct	142 ms	19508 KB	Output is correct
8	Correct	656 ms	52860 KB	Output is correct
9	Correct	686 ms	52876 KB	Output is correct
10	Correct	647 ms	52864 KB	Output is correct
11	Correct	732 ms	53052 KB	Output is correct
12	Correct	752 ms	53288 KB	Output is correct
13	Correct	808 ms	53040 KB	Output is correct
14	Correct	800 ms	52952 KB	Output is correct
15	Correct	8 ms	12748 KB	Output is correct
16	Correct	8 ms	12748 KB	Output is correct
17	Correct	7 ms	12836 KB	Output is correct
18	Correct	7 ms	12748 KB	Output is correct
19	Correct	8 ms	12876 KB	Output is correct
20	Correct	13 ms	13096 KB	Output is correct
21	Correct	94 ms	16632 KB	Output is correct
22	Correct	9 ms	12876 KB	Output is correct
23	Correct	12 ms	13088 KB	Output is correct
24	Correct	106 ms	16556 KB	Output is correct
25	Correct	115 ms	16452 KB	Output is correct
26	Correct	106 ms	16756 KB	Output is correct
27	Correct	99 ms	16636 KB	Output is correct
28	Correct	169 ms	19468 KB	Output is correct
29	Correct	1335 ms	52944 KB	Output is correct
30	Correct	162 ms	19460 KB	Output is correct
31	Correct	1396 ms	52936 KB	Output is correct
32	Correct	1111 ms	52828 KB	Output is correct
33	Correct	979 ms	52816 KB	Output is correct
34	Correct	1187 ms	53060 KB	Output is correct
35	Correct	8 ms	12748 KB	Output is correct
36	Correct	7 ms	12748 KB	Output is correct
37	Correct	104 ms	15968 KB	Output is correct
38	Correct	1047 ms	53164 KB	Output is correct
39	Correct	994 ms	52984 KB	Output is correct
40	Correct	1339 ms	56228 KB	Output is correct
41	Correct	1394 ms	56384 KB	Output is correct
42	Correct	1412 ms	56620 KB	Output is correct
43	Correct	942 ms	55904 KB	Output is correct
44	Correct	953 ms	55972 KB	Output is correct
45	Correct	763 ms	55780 KB	Output is correct
46	Correct	919 ms	55996 KB	Output is correct
47	Correct	1016 ms	56172 KB	Output is correct
48	Correct	7 ms	12748 KB	Output is correct
49	Correct	8 ms	12820 KB	Output is correct
50	Correct	10 ms	12876 KB	Output is correct
51	Correct	8 ms	12748 KB	Output is correct
52	Correct	8 ms	12748 KB	Output is correct
53	Correct	10 ms	12876 KB	Output is correct
54	Correct	28 ms	13444 KB	Output is correct
55	Correct	24 ms	13448 KB	Output is correct
56	Correct	27 ms	13764 KB	Output is correct
57	Correct	25 ms	13756 KB	Output is correct
58	Correct	25 ms	13804 KB	Output is correct
59	Correct	27 ms	13760 KB	Output is correct
60	Correct	24 ms	13776 KB	Output is correct
61	Correct	98 ms	17724 KB	Output is correct
62	Correct	143 ms	21740 KB	Output is correct
63	Correct	695 ms	55844 KB	Output is correct
64	Correct	915 ms	56084 KB	Output is correct
65	Correct	1338 ms	56232 KB	Output is correct
66	Correct	1352 ms	56428 KB	Output is correct
67	Correct	1436 ms	56644 KB	Output is correct
68	Correct	861 ms	55908 KB	Output is correct
69	Correct	1397 ms	56688 KB	Output is correct
70	Correct	992 ms	55980 KB	Output is correct
71	Correct	1054 ms	56164 KB	Output is correct
72	Correct	1346 ms	56232 KB	Output is correct
73	Correct	1460 ms	56420 KB	Output is correct
74	Correct	735 ms	55996 KB	Output is correct
75	Correct	963 ms	56132 KB	Output is correct

답안 #430570

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 14.0 / 14.0

Subtask #3 13.0 / 13.0

Subtask #4 17.0 / 17.0

Subtask #5 11.0 / 11.0

Subtask #6 15.0 / 15.0

Subtask #7 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
14.0 / 14.0

Subtask #3
13.0 / 13.0

Subtask #4
17.0 / 17.0

Subtask #5
11.0 / 11.0

Subtask #6
15.0 / 15.0

Subtask #7
25.0 / 25.0