oj.uz

답안 #48797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48797 2018-05-18T20:13:22 Z KhaledKEE 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 72 ms 4380 KB 
#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<int> t(K);
	vector<pair<int,int> > o(K);
	for(int i = 0;i < K;i++) cin>>t[i],upds(i,1),o[i] = {t[i],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;
		}
		int get = gets(out);
		if(out == 0) {
			res += (get&1?a[i].second:a[i].first);
		} else {
			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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 72 ms 4380 KB Output isn't correct
2 Halted 0 ms 0 KB -