답안 #50398 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50398	2018-06-11T00:28:50 Z	wzy	운세 보기 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #50398

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