Submission #50379

#	Time	Username	Problem	Language	Result	Execution time	Memory
50379		wzy	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	0 / 100	1324 ms	183796 KiB

fortune_telling2

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


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 *treey;

void updatevl(nd *& tree , int x , int vl, int l = 0 , int r = 1000000007){
	int mid = (l+r)/2;
	if( l== r){
		tree->sj += vl;
		return ;
	}
	if(x <= mid){
		if(tree->left == NULL) tree->left = new nd();
		updatevl(tree->left, x , vl , l , mid);
	}
	else{
		if(tree->right == NULL) tree->right = new nd();
		updatevl(tree->right , x , vl , mid + 1 , r);
	}
	int a = 0 , b = 0;
	if(tree->left != NULL){
		a += tree->left->sj;
	}
	if(tree->right != NULL){
		b += tree->right->sj;
	}
	tree->sj = a + b;
}

int queryvl(nd *& tree , int x , int y , int l = 0 , int r = 1000000007){
	int mid = (l+r)/2;
	if(l == x && r == y){
		return tree->sj;
	}
	if(y <= mid){
		if(tree->left == NULL) return 0;
		return queryvl(tree->left , x , y ,l , mid);
	}
	else if(x > mid){
		if(tree->right == NULL) return 0;
		return queryvl(tree->right , x , y , mid + 1 , r);
	}
	else{
		int a = 0 , b = 0;
		if(tree->left != NULL) a = queryvl(tree->left,  x , mid , l , mid);
		if(tree->right != NULL) b = queryvl(tree->right , mid  + 1 , y , mid + 1 , r);
		return (a  + b);
	}
}

bool cmp(card x , card y){
	if(x.b == y.b){
		return x.a > y.a;
	}
	return x.b < y.b;
}

int main(){
	scanf("%d%d" , &n , &k);
	for(int i = 0  ;i < n ; i ++){
		scanf("%d%d" , &v[i].a , &v[i].b);
		if(v[i].a > v[i].b){
			swap(v[i].a , v[i].b);
			v[i].flip = 1;
		}
	}
	treex = new node();
	treey = new nd();
	multiset< pair<int,int> > taro;
	vector<int> aa;
	for(int i = 0 ; i < k ; i++){
		int x;
		scanf("%d" , &x);
		aa.push_back(x);
		taro.insert(pair<int,int>(x , i));
		update(treex , x , i);
		updatevl(treey , x , +1);
	}
	long long ans = 0LL;
	int j =0;
	sort(v , v + n , cmp);
	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){
			v[i].newvl = 0;
			int Z = queryvl(treey , v[i].b , 1000000005);
			if(v[i].flip) Z += 1;
			if(Z%2){
				ans += v[i].b;
			}	
			else ans += v[i].a;
		}
	}
	for(int i = 0 ; i < n; i ++){
		if(v[i].newvl == 0) continue;
		int U = query(treex , v[i].a , v[i].b-1);
		while(j <= U){
			updatevl(treey, aa[j++] , -1);
		}
		int R = queryvl(treey , v[i].b , 1000000005);
		if(R%2){
			ans += v[i].a;
		}
		else ans+= v[i].b;
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" , &n , &k);
  ~~~~~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &v[i].a , &v[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &x);
   ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65