Submission #259092

#	Time	Username	Problem	Language	Result	Execution time	Memory
259092		ChrisT	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	415 ms	33496 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MN = 2e5+2;
struct three {
	int first,second,rot;
} cards[MN];
map<int,int> cmp;
pii queries[MN];
int bit[MN];
int sparse[18][MN];
void update (int n, int v) {
	for (++n;n<MN;n+=n&-n)
		bit[n] += v;
}
int query (int n) {
	int ret = 0;
	for(++n;n>0;n^=n&-n)
		ret += bit[n];
	return ret;
}
int mx (int le, int ri) {
	auto a = cmp.lower_bound(le), b = cmp.upper_bound(ri);
	if (a == cmp.end() || b == cmp.begin()) return -1;
	int l = a->second, r = (--b)->second;
	if (r < l) return -1;
	int log = 31 - __builtin_clz(r-l+1);
	return max(sparse[log][l],sparse[log][r-(1<<log)+1]);
}
int main () {
	int n,k; ll ans = 0;
	scanf ("%d %d",&n,&k);
	for (int i = 0; i < n; i++) {
		scanf ("%d %d",&cards[i].first,&cards[i].second);
		if (cards[i].first > cards[i].second) swap(cards[i].first,cards[i].second), cards[i].rot = 0;
		else cards[i].rot = 1;
	}
	sort(cards,cards+n,[](three a, three b) {return a.second > b.second;});
	for (int i = 0; i < k; i++) {
		scanf ("%d",&queries[i].first);
		queries[i].second = i;
	}
	sort(queries,queries+k,greater<pii>());
	for (int i = k-1; i >= 0; i--) {
		if (!cmp[queries[i].first]) cmp[queries[i].first] = k-1-i;
		int c = cmp[queries[i].first];
		sparse[0][c] = max(sparse[0][c],queries[i].second);
	}
	for (int len = 1; len < 18; len++) {
		for (int i = 0; i < k - (1 << len) + 1; i++) {
			sparse[len][i] = max(sparse[len-1][i],sparse[len-1][i+(1<<(len-1))]);
		}
	}
	int ind = 0;
	for (int i = 0; i < n; i++) {
		three cur = cards[i];
		while (ind < k && queries[ind].first >= cur.second) update(queries[ind++].second,1);
		int lst = cur.first == cur.second ? -1 : mx(cur.first,cur.second-1);
		int rotations = query(k) - query(lst);
		if (lst != -1) cur.rot = 0;
		ans += (cur.rot + rotations)&1 ? cur.first : cur.second;
	}
	printf ("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:33:8: 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:35:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d",&cards[i].first,&cards[i].second);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:41:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d",&queries[i].first);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65