제출 #726783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726783		parsadox2	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	527 ms	55096 KiB

fortune_telling2

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 10;
int n , k , ar[maxn];
pair<int , int> all[maxn];
bool last[maxn];

struct nod{
	vector <int> all;
} tree[(maxn << 2)];

void Build(int node = 1 , int nl = 0 , int nr = k)
{
	if(nr - nl == 1)
	{
		tree[node].all.pb(ar[nl]);
		return;
	}
	int lc = node << 1 , rc = lc | 1 , mid = (nl + nr) >> 1;
	Build(lc , nl , mid);  Build(rc , mid , nr);
	tree[node].all = tree[lc].all;
	for(auto u : tree[rc].all)  tree[node].all.pb(u);
	sort(tree[node].all.begin() , tree[node].all.end());
}

bool check(int node , int l , int r)
{
	if(tree[node].all.back() < l)  return false;
	int ps = lower_bound(tree[node].all.begin() , tree[node].all.end() , l) - tree[node].all.begin();
	return tree[node].all[ps] < r;
}

int Find_ps(int l , int r , int node = 1 , int nl = 0 , int nr = k)
{
	if(nr - nl == 1)  return nl;
	int lc = node << 1 , rc = lc | 1 , mid = (nl + nr) >> 1;
	if(check(rc , l , r))  return Find_ps(l , r , rc , mid , nr);
	else return Find_ps(l , r , lc , nl , mid);
}

int Get(int ind , int val , int node = 1 , int nl = 0 , int nr = k)
{
	if(nr <= ind)  return 0;
	if(nl >= ind)
	{
		int ps = lower_bound(tree[node].all.begin() , tree[node].all.end() , val) - tree[node].all.begin();
		return SZ(tree[node].all) - ps;
	}
	int lc = node << 1 , rc = lc | 1 , mid = (nl + nr) >> 1;
	return Get(ind , val , lc , nl , mid) + Get(ind , val , rc , mid , nr);
}

int32_t main()
{
	fast;
	cin >> n >> k;
	for(int i = 0 ; i < n ; i++)  cin >> all[i].F >> all[i].S;
	for(int i = 0 ; i < k ; i++)  cin >> ar[i];
	Build();
	ll sum = 0;
	for(int i = 0 ; i < n ; i++)
	{
		int l;
		if(!check(1 , min(all[i].F , all[i].S) , max(all[i].F , all[i].S)))  l = -1;
		else  l = Find_ps(min(all[i].F , all[i].S) , max(all[i].F , all[i].S));
		int cnt = Get(l + 1 , all[i].S);
		if(l != -1 && all[i].F < all[i].S)  swap(all[i].F , all[i].S);
		if(cnt & 1)  swap(all[i].F , all[i].S);
		sum += all[i].F;
	}
	cout << sum << endl;
	return 0;
}

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