oj.uz

Submission #754333

# Submission time Handle Problem Language Result Execution time Memory
754333 2023-06-07T13:55:58 Z jmyszka2007 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1348 ms 66748 KB 
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pi pair<int, int>
typedef long long ll;
constexpr int LIM = 2e5;
constexpr int base = (1 << 20);
map<int, int>con;
int tri[2 * base];
int tri2[2 * base];
int que(int l, int r) {
	l += base;
	r += base;
	int ans = 0;
	while(l <= r) {
		if(l & 1) {
			ans = max(ans, tri[l]);
		}
		if(!(r & 1)) {
			ans = max(ans, tri[r]);
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	return ans;
}
void upd2(int v, int x) {
	v += base;
	tri2[v] = x;
	v /= 2;
	while(v > 0) {
		tri2[v] = tri2[2 * v] + tri2[2 * v + 1];
		v /= 2;
	}
}
int que2(int l, int r) {
	l += base;
	r += base;
	int ans = 0;
	while(l <= r) {
		if(l & 1) {
			ans += tri2[l];
		}
		if(!(r & 1)) {
			ans += tri2[r];
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, t;
	cin >> n >> t;
	vector<pair<int, pi> >tab;
	for(int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		tab.push_back({max(a, b), {a, b}});
		con[a] = 0;
		con[b] = 0;
		con[a - 1] = 0;
		con[b - 1] = 0;
	}
	sort(tab.begin(), tab.end());
	reverse(tab.begin(), tab.end());
	vector<pi>zap;
	for(int i = 1; i <= t; i++) {
		int k;
		cin >> k;
		con[k] = 0;
		zap.push_back({k, i});
	}
	sort(zap.begin(), zap.end());
	reverse(zap.begin(), zap.end());
	int k = 1;
	for(auto x : con) {
		con[x.st] = k++;
	}
	for(auto x : zap) {
		tri[con[x.st] + base] = max(tri[con[x.st] + base], x.nd);
	}
	for(int i = base - 1; i >= 1; i--) {
		tri[i] = max(tri[2 * i], tri[2 * i + 1]);
	}
	k = 0;
	ll ans = 0;
	for(auto x : tab) {
		while(k < zap.size() && zap[k].st >= x.st) {
			upd2(zap[k].nd, 1);
			k++;
		}
		int kt;
		if(x.nd.st < x.nd.nd) {
			kt = que(con[x.nd.st], con[x.nd.nd - 1]);
		}
		else {
			kt = que(con[x.nd.nd], con[x.nd.st - 1]);
		}
		int a = que2(kt + 1, con.size()) & 1;
		if(!kt) {
			if(a) {
				ans += x.nd.nd;
			}
			else {
				ans += x.nd.st;
			}
		}
		else {
			if(!a) {
				ans += x.st;
			}
			else {
				ans += min(x.nd.st, x.nd.nd);
			}
		}	 
	}
	cout << ans << '\n';
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:92:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   while(k < zap.size() && zap[k].st >= x.st) {
      |         ~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4564 KB Output is correct
2 Correct 5 ms 4692 KB Output is correct
3 Correct 6 ms 4696 KB Output is correct
4 Correct 6 ms 4692 KB Output is correct
5 Correct 6 ms 4692 KB Output is correct
6 Correct 6 ms 4692 KB Output is correct
7 Correct 6 ms 4692 KB Output is correct
8 Correct 6 ms 4820 KB Output is correct
9 Correct 5 ms 4564 KB Output is correct
10 Correct 7 ms 4564 KB Output is correct
11 Correct 5 ms 4692 KB Output is correct
12 Correct 7 ms 4692 KB Output is correct
13 Correct 8 ms 4648 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4564 KB Output is correct
2 Correct 5 ms 4692 KB Output is correct
3 Correct 6 ms 4696 KB Output is correct
4 Correct 6 ms 4692 KB Output is correct
5 Correct 6 ms 4692 KB Output is correct
6 Correct 6 ms 4692 KB Output is correct
7 Correct 6 ms 4692 KB Output is correct
8 Correct 6 ms 4820 KB Output is correct
9 Correct 5 ms 4564 KB Output is correct
10 Correct 7 ms 4564 KB Output is correct
11 Correct 5 ms 4692 KB Output is correct
12 Correct 7 ms 4692 KB Output is correct
13 Correct 8 ms 4648 KB Output is correct
14 Correct 31 ms 7508 KB Output is correct
15 Correct 64 ms 10664 KB Output is correct
16 Correct 101 ms 13920 KB Output is correct
17 Correct 154 ms 16796 KB Output is correct
18 Correct 166 ms 16920 KB Output is correct
19 Correct 151 ms 16916 KB Output is correct
20 Correct 144 ms 16868 KB Output is correct
21 Correct 144 ms 16892 KB Output is correct
22 Correct 81 ms 10836 KB Output is correct
23 Correct 70 ms 9852 KB Output is correct
24 Correct 58 ms 9012 KB Output is correct
25 Correct 79 ms 11072 KB Output is correct
26 Correct 76 ms 11932 KB Output is correct
27 Correct 100 ms 12828 KB Output is correct
28 Correct 83 ms 12808 KB Output is correct
29 Correct 108 ms 14832 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4564 KB Output is correct
2 Correct 5 ms 4692 KB Output is correct
3 Correct 6 ms 4696 KB Output is correct
4 Correct 6 ms 4692 KB Output is correct
5 Correct 6 ms 4692 KB Output is correct
6 Correct 6 ms 4692 KB Output is correct
7 Correct 6 ms 4692 KB Output is correct
8 Correct 6 ms 4820 KB Output is correct
9 Correct 5 ms 4564 KB Output is correct
10 Correct 7 ms 4564 KB Output is correct
11 Correct 5 ms 4692 KB Output is correct
12 Correct 7 ms 4692 KB Output is correct
13 Correct 8 ms 4648 KB Output is correct
14 Correct 31 ms 7508 KB Output is correct
15 Correct 64 ms 10664 KB Output is correct
16 Correct 101 ms 13920 KB Output is correct
17 Correct 154 ms 16796 KB Output is correct
18 Correct 166 ms 16920 KB Output is correct
19 Correct 151 ms 16916 KB Output is correct
20 Correct 144 ms 16868 KB Output is correct
21 Correct 144 ms 16892 KB Output is correct
22 Correct 81 ms 10836 KB Output is correct
23 Correct 70 ms 9852 KB Output is correct
24 Correct 58 ms 9012 KB Output is correct
25 Correct 79 ms 11072 KB Output is correct
26 Correct 76 ms 11932 KB Output is correct
27 Correct 100 ms 12828 KB Output is correct
28 Correct 83 ms 12808 KB Output is correct
29 Correct 108 ms 14832 KB Output is correct
30 Correct 307 ms 22068 KB Output is correct
31 Correct 522 ms 31484 KB Output is correct
32 Correct 733 ms 43184 KB Output is correct
33 Correct 1348 ms 66540 KB Output is correct
34 Correct 223 ms 19664 KB Output is correct
35 Correct 1325 ms 66616 KB Output is correct
36 Correct 1298 ms 66748 KB Output is correct
37 Correct 1160 ms 66552 KB Output is correct
38 Correct 1282 ms 66668 KB Output is correct
39 Correct 1121 ms 66568 KB Output is correct
40 Correct 1028 ms 66364 KB Output is correct
41 Correct 1070 ms 66628 KB Output is correct
42 Correct 1105 ms 66620 KB Output is correct
43 Correct 522 ms 43508 KB Output is correct
44 Correct 511 ms 43656 KB Output is correct
45 Correct 512 ms 44568 KB Output is correct
46 Correct 440 ms 31092 KB Output is correct
47 Correct 376 ms 25876 KB Output is correct
48 Correct 616 ms 46316 KB Output is correct
49 Correct 598 ms 46396 KB Output is correct