Submission #50637

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
50637	2018-06-12T04:16:25 Z	wzy	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	977 ms	99064 KB

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

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.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9828 KB	Output is correct
2	Correct	10 ms	9916 KB	Output is correct
3	Correct	10 ms	9916 KB	Output is correct
4	Correct	13 ms	9916 KB	Output is correct
5	Correct	12 ms	9996 KB	Output is correct
6	Correct	11 ms	9996 KB	Output is correct
7	Correct	14 ms	9996 KB	Output is correct
8	Correct	10 ms	9996 KB	Output is correct
9	Correct	10 ms	9996 KB	Output is correct
10	Correct	10 ms	9996 KB	Output is correct
11	Correct	10 ms	9996 KB	Output is correct
12	Correct	10 ms	9996 KB	Output is correct
13	Correct	10 ms	10036 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	15160 KB	Output is correct
2	Correct	63 ms	20276 KB	Output is correct
3	Correct	100 ms	25268 KB	Output is correct
4	Correct	130 ms	30100 KB	Output is correct
5	Correct	130 ms	30220 KB	Output is correct
6	Correct	124 ms	30220 KB	Output is correct
7	Correct	137 ms	30220 KB	Output is correct
8	Correct	118 ms	30220 KB	Output is correct
9	Correct	61 ms	30220 KB	Output is correct
10	Correct	60 ms	30220 KB	Output is correct
11	Correct	59 ms	30220 KB	Output is correct
12	Correct	61 ms	30220 KB	Output is correct
13	Correct	97 ms	30220 KB	Output is correct
14	Correct	119 ms	30220 KB	Output is correct
15	Correct	121 ms	30220 KB	Output is correct
16	Correct	115 ms	30220 KB	Output is correct

Subtask #3

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	405 ms	95340 KB	Output is correct
2	Correct	493 ms	96392 KB	Output is correct
3	Correct	698 ms	97276 KB	Output is correct
4	Correct	859 ms	98712 KB	Output is correct
5	Correct	453 ms	98712 KB	Output is correct
6	Correct	883 ms	98716 KB	Output is correct
7	Correct	968 ms	98716 KB	Output is correct
8	Correct	977 ms	98780 KB	Output is correct
9	Correct	970 ms	98780 KB	Output is correct
10	Correct	883 ms	98888 KB	Output is correct
11	Correct	668 ms	98888 KB	Output is correct
12	Correct	879 ms	98888 KB	Output is correct
13	Correct	875 ms	99064 KB	Output is correct
14	Correct	470 ms	99064 KB	Output is correct
15	Correct	539 ms	99064 KB	Output is correct
16	Correct	460 ms	99064 KB	Output is correct
17	Correct	327 ms	99064 KB	Output is correct
18	Correct	300 ms	99064 KB	Output is correct
19	Correct	625 ms	99064 KB	Output is correct
20	Correct	668 ms	99064 KB	Output is correct