Submission #50389

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
50389	2018-06-10T23:45:27 Z	wzy	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	1669 ms	282428 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	8 ms	4216 KB	Output is correct
2	Correct	10 ms	4328 KB	Output is correct
3	Correct	8 ms	4380 KB	Output is correct
4	Correct	8 ms	4508 KB	Output is correct
5	Correct	8 ms	4508 KB	Output is correct
6	Correct	8 ms	4508 KB	Output is correct
7	Correct	8 ms	4508 KB	Output is correct
8	Correct	8 ms	4508 KB	Output is correct
9	Correct	8 ms	4512 KB	Output is correct
10	Correct	7 ms	4512 KB	Output is correct
11	Correct	8 ms	4640 KB	Output is correct
12	Correct	8 ms	4640 KB	Output is correct
13	Correct	8 ms	4640 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	18128 KB	Output is correct
2	Correct	127 ms	32876 KB	Output is correct
3	Correct	208 ms	47472 KB	Output is correct
4	Correct	245 ms	61648 KB	Output is correct
5	Correct	280 ms	61724 KB	Output is correct
6	Correct	249 ms	61724 KB	Output is correct
7	Correct	244 ms	61724 KB	Output is correct
8	Correct	228 ms	61836 KB	Output is correct
9	Correct	149 ms	61836 KB	Output is correct
10	Correct	216 ms	61836 KB	Output is correct
11	Correct	149 ms	61836 KB	Output is correct
12	Correct	152 ms	61836 KB	Output is correct
13	Correct	202 ms	61836 KB	Output is correct
14	Correct	223 ms	61836 KB	Output is correct
15	Correct	216 ms	61836 KB	Output is correct
16	Correct	282 ms	61836 KB	Output is correct

Subtask #3

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	982 ms	282156 KB	Output is correct
2	Correct	1268 ms	282344 KB	Output is correct
3	Correct	1293 ms	282344 KB	Output is correct
4	Correct	1599 ms	282344 KB	Output is correct
5	Correct	985 ms	282344 KB	Output is correct
6	Correct	1509 ms	282344 KB	Output is correct
7	Correct	1669 ms	282344 KB	Output is correct
8	Correct	1536 ms	282344 KB	Output is correct
9	Correct	1506 ms	282428 KB	Output is correct
10	Correct	1535 ms	282428 KB	Output is correct
11	Correct	1295 ms	282428 KB	Output is correct
12	Correct	1495 ms	282428 KB	Output is correct
13	Correct	1483 ms	282428 KB	Output is correct
14	Correct	976 ms	282428 KB	Output is correct
15	Correct	1109 ms	282428 KB	Output is correct
16	Correct	1091 ms	282428 KB	Output is correct
17	Correct	906 ms	282428 KB	Output is correct
18	Correct	1016 ms	282428 KB	Output is correct
19	Correct	1386 ms	282428 KB	Output is correct
20	Correct	1522 ms	282428 KB	Output is correct