oj.uz

Submission #48807

# Submission time Handle Problem Language Result Execution time Memory
48807 2018-05-18T22:08:48 Z KhaledKEE Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 2000 ms 3920 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<long long,long long> a,pair<long long,long long> 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<long long,long long> > a(N);
	for(int i = 0;i < N;i++) cin>>a[i].first>>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[m].first < max(a[i].first,a[i].second) && o[m].first >= min(a[i].first,a[i].second)) 
					out = max(out,o[m].second+1);
			}
		}
		int get = gets(out);
		{
			get = 0;
			for(int m = 0;m < K;m++) {
				if(o[m].first >= max(a[i].first,a[i].second) && o[m].second >= out) 
					get++;
			}
		}
		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<<endl;
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 436 KB Output is correct
3 Correct 5 ms 436 KB Output is correct
4 Correct 5 ms 440 KB Output is correct
5 Correct 5 ms 440 KB Output is correct
6 Correct 5 ms 440 KB Output is correct
7 Correct 5 ms 568 KB Output is correct
8 Correct 5 ms 656 KB Output is correct
9 Correct 5 ms 656 KB Output is correct
10 Correct 4 ms 736 KB Output is correct
11 Correct 5 ms 736 KB Output is correct
12 Correct 5 ms 736 KB Output is correct
13 Correct 6 ms 736 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 936 KB Output is correct
2 Correct 875 ms 1360 KB Output is correct
3 Correct 1790 ms 1488 KB Output is correct
4 Execution timed out 2059 ms 1872 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 3920 KB Time limit exceeded
2 Halted 0 ms 0 KB -