Submission #50637

#	Time	Username	Problem	Language	Result	Execution time	Memory
50637		wzy	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	977 ms	99064 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second

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;
	int ppos;
} v[200005];
int n , k ; 
class BIT{
	/*
	MAGIA DO GATINHO . 
  ∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
　　　　　　　　　.• ´¸.•*´¨) ¸.•*¨)
　　　　　　　　　　(¸.•´ (¸.•'* ☆
*/
public:
	void set_size(int n){
		binary_index_tree.resize(n);
	}
	int get(int x){
		if(x == 0) return 0;
		int s = 0;
		for(int i = x ; i > 0 ; i-=(i&-i)) s+= binary_index_tree[i];
		return s;
	}
	void add(int x , int vl){
		for(int i = x ; i < binary_index_tree.size() ; i+= (i&-i)) binary_index_tree[i] += vl;
	}
private :
	vector<int> binary_index_tree;
};

struct node{
	node *left = nullptr , *right = nullptr;
	int rmqid = - 1;
};
node *treex;
int rmq(node *& tree , int x , int y ,int l = 0 , int r = 1000000009){
	int mid = (l+r)/2;
	if(l == x && r == y){
		return tree->rmqid;
	}
	if(y <= mid){
		if(tree->left == nullptr) return -1;
		return rmq(tree->left,  x , y , l, mid);
	}
	else if(x > mid){
		if(tree->right == nullptr) return -1;
		return rmq(tree->right , x , y , mid + 1, r);
	}
	else{
		int a = - 1 , b = - 1;
		if(tree->left != nullptr) a = rmq(tree->left , x , mid , l ,mid);
		if(tree->right != nullptr) b = rmq(tree->right , mid + 1 , y , mid + 1 , r);
		return max(a,b);
	}
}

void update(node *& tree , int x , int vl ,int l = 0 , int r = 1000000009){
	int mid = (l+r)/2;
	if(l ==r && l ==x){
		tree->rmqid = max(tree->rmqid , vl);
		return ;
	}
	if(x <=mid){
		if(tree->left == nullptr) tree->left = new node();
		update(tree->left , x , vl , l , mid);
	}
	else{
		if(tree->right == nullptr) tree->right = new node();
		update(tree->right , x, vl , mid + 1 , r);
	}
	int a = -1 , b = -1;
	if(tree->left != nullptr) a = tree->left->rmqid;
	if(tree->right != nullptr) b = tree->right->rmqid;
	tree->rmqid = max(a,b);
}

vector<pair<int,int> > sweep[200005];
long long ans  = 0; 


int 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();
	vector<pii> rw(k);
	for(int i = 0 ; i < k ;  i ++){
		rw[i].first = readint();
		rw[i].second = i;
		update(treex , rw[i].first, rw[i].second);
	}
	BIT bitx;
	bitx.set_size(250000);
	sort(rw.begin() , rw.end());
	for(int i = 0 ; i < n ; i++){
		int pos = -1;
		if(v[i].a < v[i].b) pos = rmq(treex , v[i].a, v[i].b - 1);
		int l = 0 , r = k - 1;
		int a = -1;
		while(l<=r){
			int mid = (l+r)/2;
			if(rw[mid].first >= v[i].b){
				r = mid - 1;
				a = mid;
			}
			else l = mid + 1;
		}
		if(a != -1) sweep[a].pb(pair<int,int>(i , pos + 1));
		else{
			if(pos == -1){
				ans += (v[i].flip ? v[i].b : v[i].a);
			}
			else{
				ans += v[i].b;
			}
		}
	}
	for(int i = k - 1 ;  i >= 0 ; i--){
		bitx.add(rw[i].second + 1 , +1);
		for(int j = 0 ; j < sweep[i].size() ; j++){
			pii u = sweep[i][j];
			int L = bitx.get(200005) - bitx.get(u.second);
			if(u.second == 0){
				L += v[u.first].flip;
				if(L%2){
					ans += v[u.first].b;
				}
				else ans += v[u.first].a;
			}
			else{
				if(L%2){
					ans += v[u.first].a;
				}
				else ans += v[u.first].b;
			}
		}
	}
	printf("%lld\n" , ans);
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void BIT::add(int, int)':
fortune_telling2.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = x ; i < binary_index_tree.size() ; i+= (i&-i)) binary_index_tree[i] += vl;
                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:139:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < sweep[i].size() ; j++){
                   ~~^~~~~~~~~~~~~~~~~

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