oj.uz

Submission #74057

# Submission time Handle Problem Language Result Execution time Memory
74057 2018-08-29T16:49:29 Z kingpig9 Fortune Telling 2 (JOI14_fortune_telling2) C++11
100 / 100
 944 ms 24740 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

const int MAXN = 1 << 20;

struct segtree {
	int tr[2 * MAXN];

	void init() {
		for (int i = 0; i < 2 * MAXN; i++) {
			tr[i] = -1e9;
		}
	}

	void update (int x, int v) {
		x += MAXN;
		tr[x] = v;
		while (x >>= 1) {
			tr[x] = max(tr[2 * x], tr[2 * x + 1]);
		}
	}

	int query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
		if (rt <= a || b <= lt) {
			return -1e9;
		}

		if (a <= lt && rt <= b) {
			return tr[cur];
		}

		int mid = (lt + rt) / 2;
		return max(query(a, b, 2 * cur, lt, mid), query(a, b, 2 * cur + 1, mid, rt));
	}
};

int N, K;
pii card[MAXN];
int T[MAXN];
vector<int> vals;
segtree seg;

int main() {
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &card[i].fi, &card[i].se);
		vals.push_back(card[i].fi);
		vals.push_back(card[i].se);
	}
	for (int i = 0; i < K; i++) {
		scanf("%d", &T[i]);
		vals.push_back(T[i]);
	}
	seg.init();

	sort(all(vals));
	vals.resize(unique(all(vals)) - vals.begin());

	for (int i = 0; i < N; i++) {
		card[i].fi = lower_bound(all(vals), card[i].fi) - vals.begin();
		card[i].se = lower_bound(all(vals), card[i].se) - vals.begin();
	}
	for (int i = 0; i < K; i++) {
		T[i] = lower_bound(all(vals), T[i]) - vals.begin();
	}

	vector<pii> vt;
	for (int i = 0; i < K; i++) {
		seg.update(T[i], i);
		vt.push_back({T[i], i});
	}
	sort(all(vt));
	sort(card, card + N, [] (pii a, pii b) { return max(a.fi, a.se) > max(b.fi, b.se); });
	oset<int> certain;	//ones that are certainly going to flip the card

	ll ans = 0;
	for (int i = 0; i < N; i++) {
		int mnside = min(card[i].fi, card[i].se), mxside = max(card[i].fi, card[i].se);
		while (!vt.empty() && vt.back().fi >= mxside) {
			certain.insert(vt.back().se);
			vt.pop_back();
		}
		int x = seg.query(mnside, mxside);	//KEY IDEA: "maybe" is going to turn the card to the min. so certainly the last "maybe" will.
		bool flip = (certain.size() - certain.order_of_key(x)) % 2;
		int ind;

		if (x == -1e9) {
			ind = (flip ? card[i].se : card[i].fi);
		} else {
			ind = (flip ? mnside : mxside);
		}

		ans += vals[ind];
	}
	printf("%lld\n", ans);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &card[i].fi, &card[i].se);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &T[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8572 KB Output is correct
2 Correct 14 ms 8804 KB Output is correct
3 Correct 13 ms 8804 KB Output is correct
4 Correct 13 ms 8848 KB Output is correct
5 Correct 11 ms 8956 KB Output is correct
6 Correct 15 ms 8956 KB Output is correct
7 Correct 16 ms 8956 KB Output is correct
8 Correct 11 ms 8956 KB Output is correct
9 Correct 12 ms 8956 KB Output is correct
10 Correct 10 ms 8956 KB Output is correct
11 Correct 13 ms 9000 KB Output is correct
12 Correct 15 ms 9000 KB Output is correct
13 Correct 13 ms 9000 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8572 KB Output is correct
2 Correct 14 ms 8804 KB Output is correct
3 Correct 13 ms 8804 KB Output is correct
4 Correct 13 ms 8848 KB Output is correct
5 Correct 11 ms 8956 KB Output is correct
6 Correct 15 ms 8956 KB Output is correct
7 Correct 16 ms 8956 KB Output is correct
8 Correct 11 ms 8956 KB Output is correct
9 Correct 12 ms 8956 KB Output is correct
10 Correct 10 ms 8956 KB Output is correct
11 Correct 13 ms 9000 KB Output is correct
12 Correct 15 ms 9000 KB Output is correct
13 Correct 13 ms 9000 KB Output is correct
14 Correct 42 ms 9664 KB Output is correct
15 Correct 71 ms 10392 KB Output is correct
16 Correct 109 ms 11160 KB Output is correct
17 Correct 118 ms 12036 KB Output is correct
18 Correct 111 ms 12036 KB Output is correct
19 Correct 100 ms 12036 KB Output is correct
20 Correct 119 ms 12036 KB Output is correct
21 Correct 95 ms 12036 KB Output is correct
22 Correct 78 ms 12036 KB Output is correct
23 Correct 93 ms 12036 KB Output is correct
24 Correct 99 ms 12036 KB Output is correct
25 Correct 75 ms 12036 KB Output is correct
26 Correct 97 ms 12036 KB Output is correct
27 Correct 96 ms 12036 KB Output is correct
28 Correct 100 ms 12056 KB Output is correct
29 Correct 111 ms 12056 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8572 KB Output is correct
2 Correct 14 ms 8804 KB Output is correct
3 Correct 13 ms 8804 KB Output is correct
4 Correct 13 ms 8848 KB Output is correct
5 Correct 11 ms 8956 KB Output is correct
6 Correct 15 ms 8956 KB Output is correct
7 Correct 16 ms 8956 KB Output is correct
8 Correct 11 ms 8956 KB Output is correct
9 Correct 12 ms 8956 KB Output is correct
10 Correct 10 ms 8956 KB Output is correct
11 Correct 13 ms 9000 KB Output is correct
12 Correct 15 ms 9000 KB Output is correct
13 Correct 13 ms 9000 KB Output is correct
14 Correct 42 ms 9664 KB Output is correct
15 Correct 71 ms 10392 KB Output is correct
16 Correct 109 ms 11160 KB Output is correct
17 Correct 118 ms 12036 KB Output is correct
18 Correct 111 ms 12036 KB Output is correct
19 Correct 100 ms 12036 KB Output is correct
20 Correct 119 ms 12036 KB Output is correct
21 Correct 95 ms 12036 KB Output is correct
22 Correct 78 ms 12036 KB Output is correct
23 Correct 93 ms 12036 KB Output is correct
24 Correct 99 ms 12036 KB Output is correct
25 Correct 75 ms 12036 KB Output is correct
26 Correct 97 ms 12036 KB Output is correct
27 Correct 96 ms 12036 KB Output is correct
28 Correct 100 ms 12056 KB Output is correct
29 Correct 111 ms 12056 KB Output is correct
30 Correct 415 ms 21380 KB Output is correct
31 Correct 470 ms 22220 KB Output is correct
32 Correct 668 ms 23340 KB Output is correct
33 Correct 944 ms 24708 KB Output is correct
34 Correct 194 ms 24708 KB Output is correct
35 Correct 891 ms 24740 KB Output is correct
36 Correct 917 ms 24740 KB Output is correct
37 Correct 860 ms 24740 KB Output is correct
38 Correct 728 ms 24740 KB Output is correct
39 Correct 872 ms 24740 KB Output is correct
40 Correct 524 ms 24740 KB Output is correct
41 Correct 814 ms 24740 KB Output is correct
42 Correct 786 ms 24740 KB Output is correct
43 Correct 394 ms 24740 KB Output is correct
44 Correct 354 ms 24740 KB Output is correct
45 Correct 322 ms 24740 KB Output is correct
46 Correct 484 ms 24740 KB Output is correct
47 Correct 573 ms 24740 KB Output is correct
48 Correct 571 ms 24740 KB Output is correct
49 Correct 560 ms 24740 KB Output is correct