oj.uz

Submission #18439

# Submission time Handle Problem Language Result Execution time Memory
18439 2016-02-02T07:56:58 Z tlwpdus Fortune Telling 2 (JOI14_fortune_telling2) C++
35 / 100
 2000 ms 48800 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[1000100];
	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 23484 KB Output is correct
2 Correct 3 ms 23484 KB Output is correct
3 Correct 3 ms 23484 KB Output is correct
4 Correct 7 ms 23484 KB Output is correct
5 Correct 7 ms 23484 KB Output is correct
6 Correct 7 ms 23484 KB Output is correct
7 Correct 0 ms 23484 KB Output is correct
8 Correct 0 ms 23484 KB Output is correct
9 Correct 0 ms 23484 KB Output is correct
10 Correct 4 ms 23484 KB Output is correct
11 Correct 4 ms 23484 KB Output is correct
12 Correct 7 ms 23484 KB Output is correct
13 Correct 0 ms 23484 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24568 KB Output is correct
2 Correct 46 ms 25800 KB Output is correct
3 Correct 63 ms 26876 KB Output is correct
4 Correct 76 ms 28304 KB Output is correct
5 Correct 78 ms 28304 KB Output is correct
6 Correct 65 ms 28304 KB Output is correct
7 Correct 74 ms 28304 KB Output is correct
8 Correct 69 ms 28304 KB Output is correct
9 Correct 69 ms 28304 KB Output is correct
10 Correct 59 ms 28304 KB Output is correct
11 Correct 58 ms 28304 KB Output is correct
12 Correct 63 ms 28304 KB Output is correct
13 Correct 66 ms 28304 KB Output is correct
14 Correct 101 ms 28304 KB Output is correct
15 Correct 75 ms 28304 KB Output is correct
16 Correct 118 ms 28304 KB Output is correct

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 48800 KB Output is correct
2 Correct 223 ms 48800 KB Output is correct
3 Correct 270 ms 48800 KB Output is correct
4 Execution timed out 2000 ms 48800 KB Program timed out
5 Halted 0 ms 0 KB -