답안 #372911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
372911	2021-03-02T09:01:12 Z	Ahoora	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	558 ms	58076 KB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;

const int N = 3 * 2 * 1000 * 100 + 10, LG = 20;
int n, k, a[N], b[N], t[N], mn[N], sz, seg[N << 2], fen[N], fl[N];
vector<int> add[N];
vector<pair<int, int>> query[N];

inline void build(int l = 0, int r = sz, int id = 1) {
	if (l + 1 == r) {
		seg[id] = mn[l];
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, id << 1), build(mid, r, id << 1 | 1);
	seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}

inline int get(int s, int e, int l = 0, int r = sz, int id = 1) {
	if (s <= l && e >= r)
		return seg[id];
	if (s >= r || e <= l)
		return k;
	int mid = l + r >> 1;
	return min(get(s, e, l, mid, id << 1), get(s, e, mid, r, id << 1 | 1));
}

inline void upd(int x) {
	for (++x; x < N; x += x & -x)
		fen[x]++;
}

inline int GET(int x) {
	int res = 0;
	for (; x; x -= x & -x)
		res += fen[x];
	return res;
}

inline int inp() {
	int res = 0;
	char c = '0';
	while (c >= '0' && c <= '9') {
		((res *= 10) += c - '0');
		c = getchar();
	}
	return res;
}

int main() { 
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	n = inp(), k = inp();
	vector<int> all;
	for (int i = 0; i < n; i++) {
		a[i] = inp(), b[i] = inp();
		for (auto x: {a[i], b[i]})
			all.push_back(x);
	}
	for (int i = 0; i < k; i++)
		t[i] = inp(), all.push_back(t[i]);
	sort(all.begin(), all.end());
	all.resize(unique(all.begin(), all.end()) - all.begin());
	for (int i = 0; i < n; i++)
		for (auto x: {&a[i], &b[i]})
			*x = lower_bound(all.begin(), all.end(), *x) - all.begin();
	for (int i = 0; i < k; i++)
		t[i] = lower_bound(all.begin(), all.end(), t[i]) - all.begin();
	reverse(t, t + k);
	sz = (int)(all.size());
	for (int i = 0; i < sz; i++)
		mn[i] = k;
	for (int i = 0; i < k; i++) 
		mn[t[i]] = min(mn[t[i]], i);
	build();
	for (int i = 0; i < k; i++)
		add[t[i]].push_back(i);
	for (int i = 0; i < n; i++) {
		if (a[i] > b[i])
			swap(a[i], b[i]), fl[i]++;
		int ind = get(a[i], b[i]);
		query[b[i]].push_back({i, ind});
	}
	long long ans = 0;
	for (int i = N - 1; i >= 0; i--) {
		for (auto it: add[i]) 
			upd(it);
		for (auto it: query[i]) {
			int ind = it.second, i = it.first;
			int res = GET(ind);
			if (ind == k) {
				fl[i] += res;
			} else {
				fl[i] = 0;
				fl[i] += res;
				swap(a[i], b[i]);
			}
			ans += (fl[i] & 1? all[b[i]]: all[a[i]]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'void build(int, int, int)':
fortune_telling2.cpp:14:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |  int mid = l + r >> 1;
      |            ~~^~~
fortune_telling2.cpp: In function 'int get(int, int, int, int, int)':
fortune_telling2.cpp:24:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	28652 KB	Output is correct
2	Correct	27 ms	28652 KB	Output is correct
3	Correct	21 ms	28780 KB	Output is correct
4	Correct	21 ms	28780 KB	Output is correct
5	Correct	20 ms	28780 KB	Output is correct
6	Correct	20 ms	28780 KB	Output is correct
7	Correct	20 ms	28780 KB	Output is correct
8	Correct	20 ms	28780 KB	Output is correct
9	Correct	20 ms	28780 KB	Output is correct
10	Correct	28 ms	28780 KB	Output is correct
11	Correct	21 ms	28780 KB	Output is correct
12	Correct	28 ms	28780 KB	Output is correct
13	Correct	31 ms	28780 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	28652 KB	Output is correct
2	Correct	27 ms	28652 KB	Output is correct
3	Correct	21 ms	28780 KB	Output is correct
4	Correct	21 ms	28780 KB	Output is correct
5	Correct	20 ms	28780 KB	Output is correct
6	Correct	20 ms	28780 KB	Output is correct
7	Correct	20 ms	28780 KB	Output is correct
8	Correct	20 ms	28780 KB	Output is correct
9	Correct	20 ms	28780 KB	Output is correct
10	Correct	28 ms	28780 KB	Output is correct
11	Correct	21 ms	28780 KB	Output is correct
12	Correct	28 ms	28780 KB	Output is correct
13	Correct	31 ms	28780 KB	Output is correct
14	Correct	47 ms	29924 KB	Output is correct
15	Correct	52 ms	31216 KB	Output is correct
16	Correct	75 ms	32804 KB	Output is correct
17	Correct	109 ms	33900 KB	Output is correct
18	Correct	106 ms	33900 KB	Output is correct
19	Correct	99 ms	34008 KB	Output is correct
20	Correct	90 ms	33900 KB	Output is correct
21	Correct	86 ms	33860 KB	Output is correct
22	Correct	67 ms	33388 KB	Output is correct
23	Correct	113 ms	32748 KB	Output is correct
24	Correct	62 ms	32592 KB	Output is correct
25	Correct	68 ms	33516 KB	Output is correct
26	Correct	70 ms	33392 KB	Output is correct
27	Correct	79 ms	33644 KB	Output is correct
28	Correct	75 ms	33688 KB	Output is correct
29	Correct	88 ms	33744 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	28652 KB	Output is correct
2	Correct	27 ms	28652 KB	Output is correct
3	Correct	21 ms	28780 KB	Output is correct
4	Correct	21 ms	28780 KB	Output is correct
5	Correct	20 ms	28780 KB	Output is correct
6	Correct	20 ms	28780 KB	Output is correct
7	Correct	20 ms	28780 KB	Output is correct
8	Correct	20 ms	28780 KB	Output is correct
9	Correct	20 ms	28780 KB	Output is correct
10	Correct	28 ms	28780 KB	Output is correct
11	Correct	21 ms	28780 KB	Output is correct
12	Correct	28 ms	28780 KB	Output is correct
13	Correct	31 ms	28780 KB	Output is correct
14	Correct	47 ms	29924 KB	Output is correct
15	Correct	52 ms	31216 KB	Output is correct
16	Correct	75 ms	32804 KB	Output is correct
17	Correct	109 ms	33900 KB	Output is correct
18	Correct	106 ms	33900 KB	Output is correct
19	Correct	99 ms	34008 KB	Output is correct
20	Correct	90 ms	33900 KB	Output is correct
21	Correct	86 ms	33860 KB	Output is correct
22	Correct	67 ms	33388 KB	Output is correct
23	Correct	113 ms	32748 KB	Output is correct
24	Correct	62 ms	32592 KB	Output is correct
25	Correct	68 ms	33516 KB	Output is correct
26	Correct	70 ms	33392 KB	Output is correct
27	Correct	79 ms	33644 KB	Output is correct
28	Correct	75 ms	33688 KB	Output is correct
29	Correct	88 ms	33744 KB	Output is correct
30	Correct	165 ms	40604 KB	Output is correct
31	Correct	269 ms	45156 KB	Output is correct
32	Correct	373 ms	47900 KB	Output is correct
33	Correct	533 ms	58076 KB	Output is correct
34	Correct	144 ms	40016 KB	Output is correct
35	Correct	512 ms	57884 KB	Output is correct
36	Correct	558 ms	57992 KB	Output is correct
37	Correct	524 ms	57948 KB	Output is correct
38	Correct	508 ms	57916 KB	Output is correct
39	Correct	497 ms	57948 KB	Output is correct
40	Correct	479 ms	57948 KB	Output is correct
41	Correct	507 ms	57948 KB	Output is correct
42	Correct	498 ms	57884 KB	Output is correct
43	Correct	281 ms	57948 KB	Output is correct
44	Correct	272 ms	57948 KB	Output is correct
45	Correct	280 ms	58076 KB	Output is correct
46	Correct	270 ms	50972 KB	Output is correct
47	Correct	258 ms	47900 KB	Output is correct
48	Correct	380 ms	53084 KB	Output is correct
49	Correct	351 ms	53084 KB	Output is correct

답안 #372911

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