Submission #74057

#	Time	Username	Problem	Language	Result	Execution time	Memory
74057		kingpig9	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	944 ms	24740 KiB

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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65