oj.uz

Submission #18440

# Submission time Handle Problem Language Result Execution time Memory
18440 2016-02-02T08:06:38 Z tlwpdus Fortune Telling 2 (JOI14_fortune_telling2) C++
100 / 100
 443 ms 48992 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23676 KB Output is correct
2 Correct 0 ms 23676 KB Output is correct
3 Correct 4 ms 23676 KB Output is correct
4 Correct 2 ms 23676 KB Output is correct
5 Correct 0 ms 23676 KB Output is correct
6 Correct 7 ms 23676 KB Output is correct
7 Correct 4 ms 23676 KB Output is correct
8 Correct 3 ms 23676 KB Output is correct
9 Correct 7 ms 23676 KB Output is correct
10 Correct 0 ms 23676 KB Output is correct
11 Correct 7 ms 23676 KB Output is correct
12 Correct 3 ms 23676 KB Output is correct
13 Correct 4 ms 23676 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24760 KB Output is correct
2 Correct 45 ms 25992 KB Output is correct
3 Correct 53 ms 27068 KB Output is correct
4 Correct 80 ms 28496 KB Output is correct
5 Correct 84 ms 28496 KB Output is correct
6 Correct 62 ms 28496 KB Output is correct
7 Correct 87 ms 28496 KB Output is correct
8 Correct 74 ms 28496 KB Output is correct
9 Correct 65 ms 28496 KB Output is correct
10 Correct 58 ms 28496 KB Output is correct
11 Correct 64 ms 28496 KB Output is correct
12 Correct 55 ms 28496 KB Output is correct
13 Correct 51 ms 28496 KB Output is correct
14 Correct 99 ms 28496 KB Output is correct
15 Correct 62 ms 28496 KB Output is correct
16 Correct 98 ms 28496 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 48992 KB Output is correct
2 Correct 236 ms 48992 KB Output is correct
3 Correct 289 ms 48992 KB Output is correct
4 Correct 410 ms 48992 KB Output is correct
5 Correct 119 ms 48992 KB Output is correct
6 Correct 443 ms 48992 KB Output is correct
7 Correct 374 ms 48992 KB Output is correct
8 Correct 351 ms 48992 KB Output is correct
9 Correct 435 ms 48992 KB Output is correct
10 Correct 440 ms 48992 KB Output is correct
11 Correct 377 ms 48992 KB Output is correct
12 Correct 424 ms 48992 KB Output is correct
13 Correct 425 ms 48992 KB Output is correct
14 Correct 249 ms 48992 KB Output is correct
15 Correct 252 ms 48992 KB Output is correct
16 Correct 243 ms 48992 KB Output is correct
17 Correct 337 ms 48992 KB Output is correct
18 Correct 313 ms 48992 KB Output is correct
19 Correct 409 ms 48992 KB Output is correct
20 Correct 361 ms 48992 KB Output is correct