답안 #74057 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74057	2018-08-29T16:49:29 Z	kingpig9	운세 보기 2 (JOI14_fortune_telling2)	C++11	100 / 100	944 ms	24740 KB

fortune_telling2

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #74057

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