Submission #50388

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
50388	2018-06-10T23:45:04 Z	wzy	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	1759 ms	361872 KB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;


int readint(){
	char a = 255;
	int x = 0;
	while(!(a >= '0' && a <= '9'))a = getchar();
	while(a >= '0' && a <= '9') x = 10*x + (a - '0') , a = getchar();
	return x;
}


struct card{
	int a , b;
	bool flip = false;
	bool newvl = true;
} v[200005];
int n , k ; 

struct node{
	node *left  = NULL, *right = NULL;
	int rmqidx = -1;
} ;
node * treex ;
void update(node *&tree , int x , int vl , int l = 0 , int r = 1000000007){
	int mid = (l+r)/2;
	if(l == r){
		tree->rmqidx = max(tree->rmqidx , vl);
		return ;
	}
	if(x <= mid){
		if(tree->left == NULL) tree->left = new node();
		update(tree->left , x , vl , l , mid);
	}
	else{
		if(tree->right == NULL) tree->right = new node();
		update(tree->right, x , vl , mid + 1, r);
	}
	int xl = -1 , xr = -1;
	if(tree->left != NULL) xl = tree->left->rmqidx;
	if(tree->right != NULL) xr = tree->right->rmqidx;
	tree->rmqidx = max(xl, xr);
	return ;
}

int query(node *&tree , int x , int y , int l = 0 , int r = 1000000007 ){
	int mid = (l+r)/2;
	if(x == l && y == r){
		return tree->rmqidx;
	}
	if(y <= mid){
		if(tree->left == NULL) return -1;
		return query(tree->left, x , y , l, mid);
	}
	else if(x > mid){
		if(tree->right == NULL) return -1;
		return query(tree->right , x , y, mid + 1 , r);
	}
	else{
		int xl = -1 , xr = -1;
		if(tree->left != NULL) xl = query(tree->left, x , mid , l ,mid);
		if(tree->right != NULL) xr = query(tree->right , mid + 1 , y , mid + 1 , r);
		return max(xl, xr);
	}
}

struct nd{
	nd *left = NULL , * right = NULL;
	int sj = 0;
} ;

nd * trees[200005];

void persistent(nd *& old_version , nd *& nw , int x , int vl , int l = 0 , int r = 1000000007){
	int mid = (l+r)/2;
	if(l == r){
		nw->sj = old_version->sj;
		nw->sj += vl;
		return ;
	}
	if(x <= mid){
		nw->right = old_version->right;
		if(nw->left == NULL) nw->left = new nd();
		if(old_version->left  == NULL) persistent(trees[0] , nw->left , x , vl , l, mid);
		else persistent(old_version->left , nw->left, x , vl ,l ,mid);
	}
	else{
		nw->left = old_version->left;
		if(nw->right == NULL) nw->right = new nd();
		if(old_version->right == NULL) persistent(trees[0] , nw->right , x , vl , mid + 1 , r);
		else persistent(old_version->right , nw->right , x , vl , mid + 1 , r);
	}
	int a= 0 , b = 0;
	if(nw->left != NULL) a = nw->left->sj;
	if(nw->right != NULL) b = nw->right->sj;
	nw->sj = a + b;
}
int queryvl(nd *& treel , nd *& treer , int x , int y , int l = 0 , int r = 1000000007){
	int mid = (l+r)/2;
	if(l == x && r == y){
		return (treer->sj - treel->sj);
	}
	if(y <= mid){
		if(treer->left == NULL) return 0;
		else{
			if(treel->left == NULL) return queryvl(trees[0] , treer->left , x , y , l ,mid);
			else return queryvl(treel->left , treer->left , x , y , l ,mid);
		}
	}
	else if(x  > mid){
		if(treer->right == NULL) return 0;
		else{
			if(treel->right == NULL) return queryvl(trees[0] , treer->right , x , y, mid + 1 , r);
			else return queryvl(treel->right , treer->right , x , y, mid+ 1 , r);
		}
	}
	else{
		int a = 0 , b = 0;
		if(treer->left != NULL){
			if(treel->left == NULL) a = queryvl(trees[0] , treer->left , x , mid , l , mid);
			else a = queryvl(treel->left , treer->left , x , mid , l, mid);
		}
		if(treer->right != NULL){
			if(treel->right == NULL) b = queryvl(trees[0] , treer->right , mid +1 , y, mid +1 , r);
			else b = queryvl(treel->right , treer->right , mid + 1 , y , mid + 1 , r);
		}
		return (a+b);
	}
}

int32_t main(){
	n = readint() , k = readint();
	for(int i = 0  ;i < n ; i ++){
		v[i].a = readint() , v[i].b = readint();
		if(v[i].a > v[i].b){
			swap(v[i].a , v[i].b);
			v[i].flip = 1;
		}
	}
	treex = new node();
	trees[0] = new nd();
	for(int i = 0 ; i < k ; i++){
		int x;
		x = readint();
		update(treex , x , i);
		trees[i+1] = new nd();
		persistent(trees[i] , trees[i+1] , x , +1);
	}
	long long ans = 0LL;
	int j =0;
	for(int i = 0 ; i < n ; i ++){
		int U = -1;
		if(v[i].a < v[i].b)
		U = query(treex , v[i].a , v[i].b - 1);
		if(U == -1){
			int Z = queryvl(trees[0] , trees[k] , v[i].b , 1000000005);
			if(v[i].flip) Z += 1;
			if(Z%2){
				ans += v[i].b;
			}	
			else ans += v[i].a;
		}
		else{
			int R = queryvl(trees[U] , trees[k] , v[i].b , 1000000005);
		if(R%2){
			ans += v[i].a;
		}
		else ans += v[i].b;
		}
	}
	printf("%lld\n" , ans);
}

Compilation message

fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:151:6: warning: unused variable 'j' [-Wunused-variable]
  int j =0;
      ^

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	4216 KB	Output is correct
2	Correct	7 ms	4324 KB	Output is correct
3	Correct	8 ms	4528 KB	Output is correct
4	Correct	8 ms	4540 KB	Output is correct
5	Correct	7 ms	4540 KB	Output is correct
6	Correct	7 ms	4540 KB	Output is correct
7	Correct	8 ms	4540 KB	Output is correct
8	Correct	8 ms	4584 KB	Output is correct
9	Correct	7 ms	4584 KB	Output is correct
10	Correct	6 ms	4584 KB	Output is correct
11	Correct	7 ms	4584 KB	Output is correct
12	Correct	8 ms	4584 KB	Output is correct
13	Correct	7 ms	4584 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	18276 KB	Output is correct
2	Correct	107 ms	33016 KB	Output is correct
3	Correct	167 ms	47352 KB	Output is correct
4	Correct	223 ms	61792 KB	Output is correct
5	Correct	219 ms	61792 KB	Output is correct
6	Correct	217 ms	61792 KB	Output is correct
7	Correct	218 ms	61792 KB	Output is correct
8	Correct	204 ms	61792 KB	Output is correct
9	Correct	138 ms	61792 KB	Output is correct
10	Correct	140 ms	61792 KB	Output is correct
11	Correct	144 ms	61792 KB	Output is correct
12	Correct	162 ms	61792 KB	Output is correct
13	Correct	194 ms	61792 KB	Output is correct
14	Correct	215 ms	61792 KB	Output is correct
15	Correct	210 ms	61792 KB	Output is correct
16	Correct	262 ms	61792 KB	Output is correct

Subtask #3

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1045 ms	282284 KB	Output is correct
2	Correct	1101 ms	282316 KB	Output is correct
3	Correct	1306 ms	282528 KB	Output is correct
4	Correct	1474 ms	282528 KB	Output is correct
5	Correct	862 ms	284428 KB	Output is correct
6	Correct	1397 ms	290092 KB	Output is correct
7	Correct	1417 ms	296040 KB	Output is correct
8	Correct	1481 ms	301888 KB	Output is correct
9	Correct	1504 ms	307560 KB	Output is correct
10	Correct	1683 ms	313508 KB	Output is correct
11	Correct	1305 ms	319092 KB	Output is correct
12	Correct	1545 ms	324840 KB	Output is correct
13	Correct	1759 ms	330680 KB	Output is correct
14	Correct	1096 ms	333788 KB	Output is correct
15	Correct	1146 ms	334572 KB	Output is correct
16	Correct	1121 ms	334572 KB	Output is correct
17	Correct	1061 ms	334572 KB	Output is correct
18	Correct	977 ms	334572 KB	Output is correct
19	Correct	1403 ms	358664 KB	Output is correct
20	Correct	1315 ms	361872 KB	Output is correct