Submission #48801

#	Time	Username	Problem	Language	Result	Execution time	Memory
48801		KhaledKEE	운세 보기 2 (JOI14_fortune_telling2)	C++14	0 / 100	2005 ms	3720 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compiles and gets accepted.
 *  ___  __     _______    _______
 * |\  \|\  \  |\  ___ \  |\  ___ \
 * \ \  \/  /|_\ \   __/| \ \   __/|
 *  \ \   ___  \\ \  \_|/__\ \  \_|/__
 *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \
 *    \ \__\\ \__\\ \_______\\ \_______\
 *     \|__| \|__| \|_______| \|_______|
 */
const long long mod = 1000000007;

const int mxN = 200010;

int mBIT[mxN];
int sBIT[mxN];

void upds(int ind,int val) {
	while(ind >= 0) {
		sBIT[ind] += val;
		ind = (ind & (ind + 1)) - 1;
	}
}

void updm(int ind,int val) {
	while(ind >= 0) {
		mBIT[ind] = max(mBIT[ind],val);
		ind = (ind & (ind + 1)) - 1;
	}
}

int gets(int ind) {
	int res = 0;
	while(ind < mxN) {
		res += sBIT[ind];
		ind |= ind + 1;
	}
	return res;
}

int getm(int ind) {
	int res = 0;
	while(ind < mxN) {
		res = max(res,mBIT[ind]);
		ind |= ind + 1;
	}
	return res;
}

bool cmp(pair<int,int> a,pair<int,int> b) {
	return max(a.first,a.second) < max(b.first,b.second);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N,K;
	cin>>N>>K;
	vector<pair<int,int> > a(N);
	for(int i = 0;i < N;i++) cin>>a[i].first;
	for(int i = 0;i < N;i++) cin>>a[i].second;
	sort(a.begin(),a.end(),cmp);
	vector<pair<int,int> > o(K);
	for(int i = 0;i < K;i++) cin>>o[i].first,upds(i,1),o[i].second = i;
	sort(o.begin(),o.end());

	long long res = 0;

	for(int i = 0,j = 0;i < N;i++) {
		while(j < K && o[j].first < max(a[i].first,a[i].second)) {
			upds(o[j].second,-1);
			updm(o[j].second,o[j].first);
			j++;
		}
		int lo = 0,hi = K-1,out = 0;
		while(lo <= hi) {
			int md = (lo + hi)>>1;
			if(getm(md) >= min(a[i].first,a[i].second)) out = md + 1,lo = md + 1;
			else hi = md - 1;
		}
		{
			out = 0;
			for(int m = 0;m < K;m++) {
				if(o[i].first < max(a[i].first,a[i].second) && o[i].first >= min(a[i].first,a[i].second)) 
					out = max(out,o[i].second+1);
			}
		}
		int get = gets(out);
		if(out == 0) {
			assert(get == K - j);
			res += (get&1?a[i].second:a[i].first);
		} else {
			assert(get <= K - j);
			if(a[i].second > a[i].first) {
				res += (get&1?a[i].first:a[i].second);
			} else {
				res += (get&1?a[i].second:a[i].first);
			}
		}
	}
	cout<<res<<'\n';
	return 0;
}

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