Submission #372904

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
372904	2021-03-02T08:32:33 Z	Ahoora	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	2697 ms	165588 KB

fortune_telling2

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define indexed_set tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

using namespace __gnu_pbds;
using namespace std;

const int N = 3 * 2 * 1000 * 100 + 10, LG = 20;
int n, k, a[N], b[N], t[N], kol[N];
indexed_set fen[N];

void UPD(int id, int x) {
	kol[id]++;
	fen[id].insert(x);
}

void upd(int x, int y) {
	for (++x; x < N; x += x & -x)
		UPD(x, y);
}

int GET(int id, int x) {
	return fen[id].order_of_key(x);
}

int get(int x, int y) {
	int res = 0;
	for (; x; x -= x & -x)
		res += kol[x] - GET(x, y);
	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);
	for (int i = 0; i < k; i++)
		upd(i, t[i]);
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		int fl = 0;
		if (a[i] > b[i])
			fl++, swap(a[i], b[i]);
		int ind = 0;
		for (int j = LG - 1; j >= 0; j--) {
			if (ind + (1 << j) > k)
				continue;
			int id = ind + (1 << j);
			int x = GET(id, b[i]) - GET(id, a[i]); 
			if (x == 0) 
				ind += 1 << j;
		}
		int res = get(ind, b[i]);
		if (ind == k) {
			fl += res;
			ans += (fl & 1? all[b[i]]: all[a[i]]);
		}
		else {
			fl = 0;
			fl += res;
			swap(a[i], b[i]);
			ans += (fl & 1? all[b[i]]: all[a[i]]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	48108 KB	Output is correct
2	Correct	51 ms	48108 KB	Output is correct
3	Correct	53 ms	48108 KB	Output is correct
4	Correct	51 ms	48108 KB	Output is correct
5	Correct	51 ms	48108 KB	Output is correct
6	Correct	52 ms	48108 KB	Output is correct
7	Correct	52 ms	48108 KB	Output is correct
8	Correct	51 ms	48108 KB	Output is correct
9	Correct	53 ms	48236 KB	Output is correct
10	Correct	51 ms	48108 KB	Output is correct
11	Correct	51 ms	48128 KB	Output is correct
12	Correct	51 ms	48108 KB	Output is correct
13	Correct	53 ms	48108 KB	Output is correct

Subtask #2
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	48108 KB	Output is correct
2	Correct	51 ms	48108 KB	Output is correct
3	Correct	53 ms	48108 KB	Output is correct
4	Correct	51 ms	48108 KB	Output is correct
5	Correct	51 ms	48108 KB	Output is correct
6	Correct	52 ms	48108 KB	Output is correct
7	Correct	52 ms	48108 KB	Output is correct
8	Correct	51 ms	48108 KB	Output is correct
9	Correct	53 ms	48236 KB	Output is correct
10	Correct	51 ms	48108 KB	Output is correct
11	Correct	51 ms	48128 KB	Output is correct
12	Correct	51 ms	48108 KB	Output is correct
13	Correct	53 ms	48108 KB	Output is correct
14	Correct	112 ms	53996 KB	Output is correct
15	Correct	202 ms	60264 KB	Output is correct
16	Correct	290 ms	66040 KB	Output is correct
17	Correct	405 ms	72036 KB	Output is correct
18	Correct	402 ms	72148 KB	Output is correct
19	Correct	408 ms	72036 KB	Output is correct
20	Correct	418 ms	72164 KB	Output is correct
21	Correct	365 ms	72036 KB	Output is correct
22	Correct	304 ms	72264 KB	Output is correct
23	Correct	308 ms	72036 KB	Output is correct
24	Correct	308 ms	72224 KB	Output is correct
25	Correct	298 ms	72036 KB	Output is correct
26	Correct	326 ms	72084 KB	Output is correct
27	Correct	424 ms	72036 KB	Output is correct
28	Correct	315 ms	72056 KB	Output is correct
29	Correct	448 ms	72036 KB	Output is correct

Subtask #3
65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	48108 KB	Output is correct
2	Correct	51 ms	48108 KB	Output is correct
3	Correct	53 ms	48108 KB	Output is correct
4	Correct	51 ms	48108 KB	Output is correct
5	Correct	51 ms	48108 KB	Output is correct
6	Correct	52 ms	48108 KB	Output is correct
7	Correct	52 ms	48108 KB	Output is correct
8	Correct	51 ms	48108 KB	Output is correct
9	Correct	53 ms	48236 KB	Output is correct
10	Correct	51 ms	48108 KB	Output is correct
11	Correct	51 ms	48128 KB	Output is correct
12	Correct	51 ms	48108 KB	Output is correct
13	Correct	53 ms	48108 KB	Output is correct
14	Correct	112 ms	53996 KB	Output is correct
15	Correct	202 ms	60264 KB	Output is correct
16	Correct	290 ms	66040 KB	Output is correct
17	Correct	405 ms	72036 KB	Output is correct
18	Correct	402 ms	72148 KB	Output is correct
19	Correct	408 ms	72036 KB	Output is correct
20	Correct	418 ms	72164 KB	Output is correct
21	Correct	365 ms	72036 KB	Output is correct
22	Correct	304 ms	72264 KB	Output is correct
23	Correct	308 ms	72036 KB	Output is correct
24	Correct	308 ms	72224 KB	Output is correct
25	Correct	298 ms	72036 KB	Output is correct
26	Correct	326 ms	72084 KB	Output is correct
27	Correct	424 ms	72036 KB	Output is correct
28	Correct	315 ms	72056 KB	Output is correct
29	Correct	448 ms	72036 KB	Output is correct
30	Correct	1232 ms	158660 KB	Output is correct
31	Correct	1524 ms	160092 KB	Output is correct
32	Correct	1883 ms	161756 KB	Output is correct
33	Correct	2569 ms	165460 KB	Output is correct
34	Correct	1171 ms	158304 KB	Output is correct
35	Correct	2601 ms	165416 KB	Output is correct
36	Correct	2589 ms	165460 KB	Output is correct
37	Correct	2596 ms	165588 KB	Output is correct
38	Correct	2569 ms	165576 KB	Output is correct
39	Correct	2697 ms	165460 KB	Output is correct
40	Correct	2071 ms	165232 KB	Output is correct
41	Correct	2678 ms	165460 KB	Output is correct
42	Correct	2613 ms	165392 KB	Output is correct
43	Correct	1545 ms	164828 KB	Output is correct
44	Correct	1554 ms	164692 KB	Output is correct
45	Correct	1549 ms	164948 KB	Output is correct
46	Correct	1604 ms	163580 KB	Output is correct
47	Correct	1594 ms	163280 KB	Output is correct
48	Correct	1974 ms	165460 KB	Output is correct
49	Correct	1748 ms	165460 KB	Output is correct

Submission #372904

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