답안 #50386 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50386	2018-06-10T23:38:59 Z	wzy	운세 보기 2 (JOI14_fortune_telling2)	C++11	35 / 100	2000 ms	310824 KB

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 * trees[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(){
	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();
	trees[0] = new nd();
	vector<int> aa;
	for(int i = 0 ; i < k ; i++){
		int x;
		scanf("%d" , &x);
		aa.push_back(x);
		update(treex , x , i);
		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 = -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(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;
		}
	}
	for(int i = 0 ; i < n; i ++){
		if(v[i].newvl == 0) continue;
		int U = query(treex , v[i].a , v[i].b-1);
		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:144:6: warning: unused variable 'j' [-Wunused-variable]
  int j =0;
      ^
fortune_telling2.cpp:124: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:126: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:137:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &x);
   ~~~~~^~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	4344 KB	Output is correct
2	Correct	8 ms	4428 KB	Output is correct
3	Correct	9 ms	4428 KB	Output is correct
4	Correct	9 ms	4496 KB	Output is correct
5	Correct	9 ms	4584 KB	Output is correct
6	Correct	9 ms	4688 KB	Output is correct
7	Correct	8 ms	4716 KB	Output is correct
8	Correct	9 ms	4764 KB	Output is correct
9	Correct	8 ms	4836 KB	Output is correct
10	Correct	8 ms	4836 KB	Output is correct
11	Correct	9 ms	4952 KB	Output is correct
12	Correct	9 ms	4988 KB	Output is correct
13	Correct	9 ms	5020 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	18748 KB	Output is correct
2	Correct	135 ms	34100 KB	Output is correct
3	Correct	207 ms	49408 KB	Output is correct
4	Correct	310 ms	65036 KB	Output is correct
5	Correct	364 ms	66192 KB	Output is correct
6	Correct	321 ms	67352 KB	Output is correct
7	Correct	268 ms	68460 KB	Output is correct
8	Correct	262 ms	69828 KB	Output is correct
9	Correct	195 ms	69828 KB	Output is correct
10	Correct	201 ms	69828 KB	Output is correct
11	Correct	188 ms	69828 KB	Output is correct
12	Correct	198 ms	69828 KB	Output is correct
13	Correct	217 ms	73224 KB	Output is correct
14	Correct	253 ms	74688 KB	Output is correct
15	Correct	257 ms	75328 KB	Output is correct
16	Correct	240 ms	76960 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1004 ms	298220 KB	Output is correct
2	Correct	1287 ms	301192 KB	Output is correct
3	Correct	1427 ms	304948 KB	Output is correct
4	Execution timed out	2031 ms	310824 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

답안 #50386

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
0 / 65.0