oj.uz

Submission #48808

# Submission time Handle Problem Language Result Execution time Memory
48808 2018-05-18T22:09:37 Z KhaledKEE Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 276 ms 7000 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 3 ms 556 KB Output is correct
3 Correct 3 ms 556 KB Output is correct
4 Correct 3 ms 556 KB Output is correct
5 Correct 3 ms 556 KB Output is correct
6 Correct 3 ms 556 KB Output is correct
7 Correct 3 ms 660 KB Output is correct
8 Correct 4 ms 660 KB Output is correct
9 Correct 4 ms 660 KB Output is correct
10 Correct 2 ms 660 KB Output is correct
11 Correct 11 ms 660 KB Output is correct
12 Correct 3 ms 660 KB Output is correct
13 Correct 4 ms 660 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 840 KB Output is correct
2 Correct 21 ms 1144 KB Output is correct
3 Correct 30 ms 1464 KB Output is correct
4 Correct 41 ms 1848 KB Output is correct
5 Correct 39 ms 1852 KB Output is correct
6 Correct 39 ms 1852 KB Output is correct
7 Correct 42 ms 1852 KB Output is correct
8 Correct 49 ms 1852 KB Output is correct
9 Correct 34 ms 1892 KB Output is correct
10 Correct 33 ms 2008 KB Output is correct
11 Correct 35 ms 2008 KB Output is correct
12 Correct 32 ms 2008 KB Output is correct
13 Correct 34 ms 2008 KB Output is correct
14 Correct 50 ms 2008 KB Output is correct
15 Correct 39 ms 2008 KB Output is correct
16 Correct 48 ms 2008 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 3924 KB Output is correct
2 Correct 98 ms 4616 KB Output is correct
3 Correct 128 ms 5284 KB Output is correct
4 Correct 199 ms 6892 KB Output is correct
5 Correct 69 ms 6892 KB Output is correct
6 Correct 190 ms 7000 KB Output is correct
7 Correct 189 ms 7000 KB Output is correct
8 Correct 194 ms 7000 KB Output is correct
9 Correct 190 ms 7000 KB Output is correct
10 Correct 203 ms 7000 KB Output is correct
11 Correct 184 ms 7000 KB Output is correct
12 Correct 190 ms 7000 KB Output is correct
13 Correct 276 ms 7000 KB Output is correct
14 Correct 258 ms 7000 KB Output is correct
15 Correct 155 ms 7000 KB Output is correct
16 Correct 164 ms 7000 KB Output is correct
17 Correct 168 ms 7000 KB Output is correct
18 Correct 190 ms 7000 KB Output is correct
19 Correct 198 ms 7000 KB Output is correct
20 Correct 200 ms 7000 KB Output is correct