oj.uz

Submission #372911

# Submission time Handle Problem Language Result Execution time Memory
372911 2021-03-02T09:01:12 Z Ahoora Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 558 ms 58076 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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