Submission #50398

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
50398	2018-06-11T00:28:50 Z	wzy	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	35 / 100	2000 ms	277052 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);
	}
}

void dfs(node *& treex , int l = 0 , int r = 1000000007){
	int mid = (l+r)/2;
	if(l == r){
		delete treex;
		return ;
	}
	if(treex->left != NULL) dfs(treex->left, l ,mid);
	if(treex->right != NULL) dfs(treex->right , mid + 1 , r);
	return ;
}

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;
	}
	dfs(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:174: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	8 ms	4324 KB	Output is correct
3	Correct	9 ms	4532 KB	Output is correct
4	Correct	10 ms	4564 KB	Output is correct
5	Correct	12 ms	4564 KB	Output is correct
6	Correct	9 ms	4564 KB	Output is correct
7	Correct	11 ms	4564 KB	Output is correct
8	Correct	8 ms	4564 KB	Output is correct
9	Correct	7 ms	4564 KB	Output is correct
10	Correct	6 ms	4564 KB	Output is correct
11	Correct	8 ms	4564 KB	Output is correct
12	Correct	8 ms	4564 KB	Output is correct
13	Correct	8 ms	4564 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	17988 KB	Output is correct
2	Correct	108 ms	32480 KB	Output is correct
3	Correct	173 ms	46600 KB	Output is correct
4	Correct	225 ms	60704 KB	Output is correct
5	Correct	244 ms	60740 KB	Output is correct
6	Correct	254 ms	60740 KB	Output is correct
7	Correct	258 ms	60740 KB	Output is correct
8	Correct	316 ms	60740 KB	Output is correct
9	Correct	191 ms	60740 KB	Output is correct
10	Correct	157 ms	60740 KB	Output is correct
11	Correct	156 ms	60740 KB	Output is correct
12	Correct	147 ms	60740 KB	Output is correct
13	Correct	247 ms	60740 KB	Output is correct
14	Correct	255 ms	60740 KB	Output is correct
15	Correct	252 ms	60740 KB	Output is correct
16	Correct	291 ms	60740 KB	Output is correct

Subtask #3

0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1123 ms	276220 KB	Output is correct
2	Correct	1139 ms	276380 KB	Output is correct
3	Correct	1252 ms	276504 KB	Output is correct
4	Correct	1480 ms	277052 KB	Output is correct
5	Correct	1077 ms	277052 KB	Output is correct
6	Correct	1543 ms	277052 KB	Output is correct
7	Correct	1415 ms	277052 KB	Output is correct
8	Correct	1524 ms	277052 KB	Output is correct
9	Correct	1932 ms	277052 KB	Output is correct
10	Execution timed out	2023 ms	277052 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-