Submission #50392

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
50392	2018-06-11T00:15:06 Z	wzy	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	1558 ms	283260 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;
} 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];

int Uvl[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();
	queue<int> ww;
	for(int i = 0 ; i < k ; i++){
		int x;
		x = readint();
		ww.push(x);
		update(treex , x , i);
	}
	for(int i = 0 ; i < n; i ++){
		if(v[i].a < v[i].b)
		Uvl[i] = query(treex , v[i].a , v[i].b - 1);
		else Uvl[i] = -1;
	}
	delete treex;
	for(int i = 0 ; i < k ; i++){
		int x = ww.front();
		ww.pop();
		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 = Uvl[i];
		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:163: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	4344 KB	Output is correct
2	Correct	7 ms	4344 KB	Output is correct
3	Correct	8 ms	4396 KB	Output is correct
4	Correct	8 ms	4396 KB	Output is correct
5	Correct	9 ms	4448 KB	Output is correct
6	Correct	8 ms	4584 KB	Output is correct
7	Correct	8 ms	4584 KB	Output is correct
8	Correct	9 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	8 ms	4604 KB	Output is correct
12	Correct	7 ms	4604 KB	Output is correct
13	Correct	9 ms	4604 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	18300 KB	Output is correct
2	Correct	119 ms	33024 KB	Output is correct
3	Correct	170 ms	47576 KB	Output is correct
4	Correct	242 ms	61820 KB	Output is correct
5	Correct	207 ms	61960 KB	Output is correct
6	Correct	206 ms	61960 KB	Output is correct
7	Correct	203 ms	61960 KB	Output is correct
8	Correct	196 ms	61960 KB	Output is correct
9	Correct	143 ms	61960 KB	Output is correct
10	Correct	141 ms	61960 KB	Output is correct
11	Correct	134 ms	61960 KB	Output is correct
12	Correct	144 ms	61960 KB	Output is correct
13	Correct	202 ms	61960 KB	Output is correct
14	Correct	198 ms	61960 KB	Output is correct
15	Correct	194 ms	61960 KB	Output is correct
16	Correct	206 ms	61960 KB	Output is correct

Subtask #3

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	914 ms	282352 KB	Output is correct
2	Correct	929 ms	282628 KB	Output is correct
3	Correct	1014 ms	282752 KB	Output is correct
4	Correct	1249 ms	283216 KB	Output is correct
5	Correct	808 ms	283216 KB	Output is correct
6	Correct	1222 ms	283216 KB	Output is correct
7	Correct	1376 ms	283256 KB	Output is correct
8	Correct	1279 ms	283256 KB	Output is correct
9	Correct	1271 ms	283256 KB	Output is correct
10	Correct	1250 ms	283256 KB	Output is correct
11	Correct	1299 ms	283260 KB	Output is correct
12	Correct	1558 ms	283260 KB	Output is correct
13	Correct	1443 ms	283260 KB	Output is correct
14	Correct	1048 ms	283260 KB	Output is correct
15	Correct	1033 ms	283260 KB	Output is correct
16	Correct	1039 ms	283260 KB	Output is correct
17	Correct	804 ms	283260 KB	Output is correct
18	Correct	767 ms	283260 KB	Output is correct
19	Correct	1126 ms	283260 KB	Output is correct
20	Correct	1186 ms	283260 KB	Output is correct