답안 #85557 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
85557	2018-11-20T22:52:10 Z	luciocf	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	596 ms	162576 KB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+5;

typedef long long ll;

int num[2][maxn], query[maxn];

vector<int> tree[4*maxn];

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node].push_back(query[l]);
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	int a = 2*node, b = 2*node+1;
	merge(tree[a].begin(), tree[a].end(), tree[b].begin(), tree[b].end(), back_inserter(tree[node]));
}

int query_pos(int node, int l, int r, int a, int b)
{
	if (l == r) 
		return ((tree[node][0] >= a && tree[node][0] < b) ? l : -1);

	int mid = (l+r)>>1;

	if (tree[2*node+1].back() < a)
		return query_pos(2*node, l, mid, a, b);

	if (*(lower_bound(tree[2*node+1].begin(), tree[2*node+1].end(), a)) < b)
		return query_pos(2*node+1, mid+1, r, a, b);

	return query_pos(2*node, l, mid, a, b);
}

int query_qtd(int node, int l, int r, int a, int b, int vv)
{
	if (a > b) return 0;
	if (l > b || r < a) return 0;

	if (l >= a && r <= b) 
		return (tree[node].end()-lower_bound(tree[node].begin(), tree[node].end(), vv));

	int mid = (l+r)>>1;

	return (query_qtd(2*node, l, mid, a, b, vv)+query_qtd(2*node+1, mid+1, r, a, b, vv));
}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);

	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++)
		cin >> num[0][i] >> num[1][i];

	for (int i = 1; i <= k; i++)
		cin >> query[i];

	build(1, 1, k);

	ll ans = 0LL;
	for (int i = 1; i <= n; i++)
	{
		int A = max(num[0][i], num[1][i]), B = min(num[0][i], num[1][i]);
		int last = query_pos(1, 1, k, B, A);

		if (last == -1)
		{
			int qtd = query_qtd(1, 1, k, 1, k, num[0][i]);

			if (qtd%2 == 0) ans += (ll)num[0][i];
			else ans += (ll)num[1][i];
		}
		else
		{
			int qtd = query_qtd(1, 1, k, last+1, k, A);

			if (qtd%2 == 0) ans += (ll)A;
			else ans += (ll)B;
		}
	}

	cout << ans << "\n";
}

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	19192 KB	Output is correct
2	Correct	19 ms	19316 KB	Output is correct
3	Correct	23 ms	19572 KB	Output is correct
4	Correct	20 ms	19728 KB	Output is correct
5	Correct	20 ms	19760 KB	Output is correct
6	Correct	21 ms	19760 KB	Output is correct
7	Correct	21 ms	19780 KB	Output is correct
8	Correct	19 ms	19852 KB	Output is correct
9	Correct	20 ms	19916 KB	Output is correct
10	Correct	20 ms	19916 KB	Output is correct
11	Correct	19 ms	19988 KB	Output is correct
12	Correct	21 ms	20020 KB	Output is correct
13	Correct	21 ms	20052 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	19192 KB	Output is correct
2	Correct	19 ms	19316 KB	Output is correct
3	Correct	23 ms	19572 KB	Output is correct
4	Correct	20 ms	19728 KB	Output is correct
5	Correct	20 ms	19760 KB	Output is correct
6	Correct	21 ms	19760 KB	Output is correct
7	Correct	21 ms	19780 KB	Output is correct
8	Correct	19 ms	19852 KB	Output is correct
9	Correct	20 ms	19916 KB	Output is correct
10	Correct	20 ms	19916 KB	Output is correct
11	Correct	19 ms	19988 KB	Output is correct
12	Correct	21 ms	20020 KB	Output is correct
13	Correct	21 ms	20052 KB	Output is correct
14	Correct	37 ms	21876 KB	Output is correct
15	Correct	54 ms	23836 KB	Output is correct
16	Correct	73 ms	25692 KB	Output is correct
17	Correct	98 ms	29128 KB	Output is correct
18	Correct	118 ms	30220 KB	Output is correct
19	Correct	94 ms	31448 KB	Output is correct
20	Correct	106 ms	32600 KB	Output is correct
21	Correct	82 ms	33732 KB	Output is correct
22	Correct	67 ms	34404 KB	Output is correct
23	Correct	66 ms	35108 KB	Output is correct
24	Correct	73 ms	35780 KB	Output is correct
25	Correct	64 ms	36460 KB	Output is correct
26	Correct	71 ms	37432 KB	Output is correct
27	Correct	110 ms	38644 KB	Output is correct
28	Correct	71 ms	39796 KB	Output is correct
29	Correct	121 ms	41008 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	19192 KB	Output is correct
2	Correct	19 ms	19316 KB	Output is correct
3	Correct	23 ms	19572 KB	Output is correct
4	Correct	20 ms	19728 KB	Output is correct
5	Correct	20 ms	19760 KB	Output is correct
6	Correct	21 ms	19760 KB	Output is correct
7	Correct	21 ms	19780 KB	Output is correct
8	Correct	19 ms	19852 KB	Output is correct
9	Correct	20 ms	19916 KB	Output is correct
10	Correct	20 ms	19916 KB	Output is correct
11	Correct	19 ms	19988 KB	Output is correct
12	Correct	21 ms	20020 KB	Output is correct
13	Correct	21 ms	20052 KB	Output is correct
14	Correct	37 ms	21876 KB	Output is correct
15	Correct	54 ms	23836 KB	Output is correct
16	Correct	73 ms	25692 KB	Output is correct
17	Correct	98 ms	29128 KB	Output is correct
18	Correct	118 ms	30220 KB	Output is correct
19	Correct	94 ms	31448 KB	Output is correct
20	Correct	106 ms	32600 KB	Output is correct
21	Correct	82 ms	33732 KB	Output is correct
22	Correct	67 ms	34404 KB	Output is correct
23	Correct	66 ms	35108 KB	Output is correct
24	Correct	73 ms	35780 KB	Output is correct
25	Correct	64 ms	36460 KB	Output is correct
26	Correct	71 ms	37432 KB	Output is correct
27	Correct	110 ms	38644 KB	Output is correct
28	Correct	71 ms	39796 KB	Output is correct
29	Correct	121 ms	41008 KB	Output is correct
30	Correct	200 ms	65388 KB	Output is correct
31	Correct	250 ms	68576 KB	Output is correct
32	Correct	368 ms	72864 KB	Output is correct
33	Correct	596 ms	79560 KB	Output is correct
34	Correct	176 ms	79808 KB	Output is correct
35	Correct	508 ms	87172 KB	Output is correct
36	Correct	505 ms	93224 KB	Output is correct
37	Correct	510 ms	99052 KB	Output is correct
38	Correct	477 ms	104628 KB	Output is correct
39	Correct	525 ms	110476 KB	Output is correct
40	Correct	370 ms	116032 KB	Output is correct
41	Correct	499 ms	121844 KB	Output is correct
42	Correct	552 ms	127708 KB	Output is correct
43	Correct	288 ms	132928 KB	Output is correct
44	Correct	255 ms	138032 KB	Output is correct
45	Correct	254 ms	143024 KB	Output is correct
46	Correct	277 ms	146928 KB	Output is correct
47	Correct	307 ms	150872 KB	Output is correct
48	Correct	321 ms	156580 KB	Output is correct
49	Correct	289 ms	162576 KB	Output is correct

답안 #85557

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 65.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
65.0 / 65.0