Submission #18440

#	Time	Username	Problem	Language	Result	Execution time	Memory
18440		tlwpdus	Fortune Telling 2 (JOI14_fortune_telling2)	C++98	100 / 100	443 ms	48992 KiB

fortune_telling2

#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

int n, k;
int a[200100], b[200100], q[200100];
int ia[200100], ib[200100];
int all[400100], m;

struct idxtree {
	int tree[1050000];
	int key;
	void init(int n) {
		key = 1;
		while(key<n) key*=2;
		for (int i=0;i<key*2;i++) tree[i] = -1;
	}
	void update(int idx, int val) {
		idx+=key;
		tree[idx] = max(tree[idx],val);
		idx/=2;
		while(idx>0) {
			tree[idx] = max(tree[idx*2],tree[idx*2+1]);
			idx/=2;
		}
	}
	int query(int s, int e) {
		int res = -1;
		s+=key;
		e+=key;
		while(s<=e) {
			if (s%2==1) res = max(res,tree[s++]);
			if (e%2==0) res = max(res,tree[e--]);
			s >>= 1;
			e >>= 1;
		}
		return res;
	}
} it;

struct vectortree {
	vector<int> tree[550000];
	int key;
	void init(int n) {
		key = 1;
		while(key<n) key*=2;
		for (int i=0;i<key*2;i++) tree[i].clear();
	}
	void update(int idx, int val) {
		idx+=key;
		tree[idx].push_back(val);
	}
	void merge() {
		int i;
		for (i=key-1;i>0;i--) {
			int l = 2*i, r = 2*i+1;
			int kl = 0, kr = 0;
			while(kl<tree[l].size()&&kr<tree[r].size()) {
				if (tree[l][kl]<tree[r][kr]) tree[i].push_back(tree[l][kl++]);
				else tree[i].push_back(tree[r][kr++]);
			}
			if (kl<tree[l].size()) for (;kl<tree[l].size();kl++) tree[i].push_back(tree[l][kl]);
			if (kr<tree[r].size()) for (;kr<tree[r].size();kr++) tree[i].push_back(tree[r][kr]);
		}
	}
	int query(int s, int e, int val) { // [s,e] 에서 val 이상의 개수
		int res = 0;
		s+=key;
		e+=key;
		while(s<=e) {
			if (s%2==1) {res += tree[s].end()-lower_bound(tree[s].begin(),tree[s].end(),val);s++;}
			if (e%2==0) {res += tree[e].end()-lower_bound(tree[e].begin(),tree[e].end(),val);e--;}
			s >>= 1;
			e >>= 1;
		}
		return res;
	}
} vit;

void process() {
	int i;
	for (i=0;i<n;i++) {
		all[i*2] = a[i];
		all[i*2+1] = b[i];
	}
	sort(all,all+2*n);
	m = unique(all,all+2*n)-all;
	for (i=0;i<n;i++) {
		ia[i] = lower_bound(all,all+m,a[i])-all;
		ib[i] = lower_bound(all,all+m,b[i])-all;
	}
	it.init(m+2);
	vit.init(k+2);
	for (i=0;i<k;i++) {
		int iq = upper_bound(all,all+m,q[i])-all-1;
		vit.update(i,iq);
		if (iq==-1) continue;
		it.update(iq,i);
	}
	vit.merge();
	long long sum = 0;
	for (i=0;i<n;i++) {
		int idx = it.query(min(ia[i],ib[i]),max(ia[i],ib[i])-1);
		int res = vit.query(idx+1,k-1,max(ia[i],ib[i]));
		if (idx==-1||a[i]>=b[i]) {
			if (res%2==0) sum+=(long long)a[i];
			else sum+=(long long)b[i];
		}
		else {
			if (res%2==0) sum+=(long long)b[i];
			else sum+=(long long)a[i];
		}
	}
	printf("%lld\n",sum);
}

void input() {
	int i;
	
	scanf("%d %d",&n,&k);
	for (i=0;i<n;i++) scanf("%d %d",&a[i],&b[i]);
	for (i=0;i<k;i++) scanf("%d",&q[i]);
	
}

int main() {
	input();
	process();
	return 0;
}

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