답안 #52209 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52209	2018-06-25T04:57:37 Z	김세빈(#1347)	운세 보기 2 (JOI14_fortune_telling2)	C++11	35 / 100	206 ms	126064 KB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

struct node{
	int l,r,v;
	node() { l = r = v = 0;}
};

node T[5050505];
vector <int> V;
int R[202020], M[202020];
int K[202020];
int A[202020], B[202020];
int n,m,k,sz,t;
long long ans;

void pst_insert(int p, int s, int e, int v)
{
	T[p].v ++;
	
	if(s == e) return;
	
	int mid = (s+e) >> 1;
	if(v <= mid){
		T[++t] = T[T[p].l]; T[p].l = t;
		pst_insert(t, s, mid, v);
	}
	else{
		T[++t] = T[T[p].r]; T[p].r = t;
		pst_insert(t, mid+1, e, v);
	}
}

int pst_query(int p, int s, int e, int l, int r)
{
	if(!p || r < s || e < l) return 0;
	if(l <= s && e <= r) return T[p].v;
	
	int mid = (s+e) >> 1;
	return pst_query(T[p].l, s, mid, l, r) + pst_query(T[p].r, mid+1, e, l, r);
}

void insert(int p,int v)
{
	p += sz;
	M[p] = max(M[p], v);
	
	for(p>>=1;p;p>>=1){
		M[p] = max(M[p<<1], M[p<<1|1]);
	}
}

int max_idx(int l,int r)
{
	int ret = -1;
	l += sz, r += sz;
	
	for(;l<r;){
		if(l & 1) ret = max(ret, M[l]);
		if(~r & 1) ret = max(ret, M[r]);
		l = ++l >> 1;
		r = --r >> 1;
	}
	if(l == r) ret = max(ret, M[l]);
	
	return ret;
}

int main()
{
	int i,l,r,p,x;
	
	scanf("%d%d",&n,&k);
	
	for(i=0;i<n;i++){
		scanf("%d%d",A+i,B+i);
	}
	
	for(i=0;i<k;i++){
		scanf("%d",K+i);
		V.push_back(K[i]);
	}
	
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	
	m = V.size();
	for(sz=1;sz<m;sz<<=1);
	
	for(i=1;i<sz+sz;i++) M[i] = -1;
	
	for(i=k-1;i>=0;i--){
		K[i] = lower_bound(V.begin(), V.end(), K[i]) - V.begin();
		
		T[++t] = T[R[i+1]]; R[i] = t;
		pst_insert(R[i], 0, m-1, K[i]);
		
		insert(K[i], i);
	}
	
	for(i=0;i<n;i++){
		l = min(A[i], B[i]);
		r = max(A[i], B[i]);
		l = lower_bound(V.begin(), V.end(), l) - V.begin();
		r = lower_bound(V.begin(), V.end(), r) - V.begin() - 1;
		
		p = max_idx(l, r);
		x = p == -1? 1 : A[i] > B[i];
		
		x ^= (pst_query(R[p+1], 0, m-1, r+1, m-1) % 2);
		
		ans += x? A[i] : B[i];
	}
	
	printf("%lld\n",ans);
	
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int max_idx(int, int)':
fortune_telling2.cpp:62:5: warning: operation on 'l' may be undefined [-Wsequence-point]
   l = ++l >> 1;
   ~~^~~~~~~~~~
fortune_telling2.cpp:63:5: warning: operation on 'r' may be undefined [-Wsequence-point]
   r = --r >> 1;
   ~~^~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:74: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:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",A+i,B+i);
   ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",K+i);
   ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	59640 KB	Output is correct
2	Correct	54 ms	59792 KB	Output is correct
3	Correct	49 ms	59828 KB	Output is correct
4	Correct	49 ms	59876 KB	Output is correct
5	Correct	49 ms	59876 KB	Output is correct
6	Correct	50 ms	59876 KB	Output is correct
7	Correct	50 ms	59912 KB	Output is correct
8	Correct	49 ms	59912 KB	Output is correct
9	Correct	49 ms	59912 KB	Output is correct
10	Correct	50 ms	59912 KB	Output is correct
11	Correct	52 ms	59912 KB	Output is correct
12	Correct	57 ms	59912 KB	Output is correct
13	Correct	67 ms	59980 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	59640 KB	Output is correct
2	Correct	54 ms	59792 KB	Output is correct
3	Correct	49 ms	59828 KB	Output is correct
4	Correct	49 ms	59876 KB	Output is correct
5	Correct	49 ms	59876 KB	Output is correct
6	Correct	50 ms	59876 KB	Output is correct
7	Correct	50 ms	59912 KB	Output is correct
8	Correct	49 ms	59912 KB	Output is correct
9	Correct	49 ms	59912 KB	Output is correct
10	Correct	50 ms	59912 KB	Output is correct
11	Correct	52 ms	59912 KB	Output is correct
12	Correct	57 ms	59912 KB	Output is correct
13	Correct	67 ms	59980 KB	Output is correct
14	Correct	72 ms	60152 KB	Output is correct
15	Correct	79 ms	60588 KB	Output is correct
16	Correct	90 ms	60900 KB	Output is correct
17	Correct	119 ms	61408 KB	Output is correct
18	Correct	136 ms	61408 KB	Output is correct
19	Correct	127 ms	61408 KB	Output is correct
20	Correct	110 ms	61408 KB	Output is correct
21	Correct	104 ms	61408 KB	Output is correct
22	Correct	89 ms	61408 KB	Output is correct
23	Correct	88 ms	61408 KB	Output is correct
24	Correct	89 ms	61408 KB	Output is correct
25	Correct	93 ms	61448 KB	Output is correct
26	Correct	122 ms	61448 KB	Output is correct
27	Correct	106 ms	61448 KB	Output is correct
28	Correct	98 ms	61448 KB	Output is correct
29	Correct	151 ms	61492 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	59640 KB	Output is correct
2	Correct	54 ms	59792 KB	Output is correct
3	Correct	49 ms	59828 KB	Output is correct
4	Correct	49 ms	59876 KB	Output is correct
5	Correct	49 ms	59876 KB	Output is correct
6	Correct	50 ms	59876 KB	Output is correct
7	Correct	50 ms	59912 KB	Output is correct
8	Correct	49 ms	59912 KB	Output is correct
9	Correct	49 ms	59912 KB	Output is correct
10	Correct	50 ms	59912 KB	Output is correct
11	Correct	52 ms	59912 KB	Output is correct
12	Correct	57 ms	59912 KB	Output is correct
13	Correct	67 ms	59980 KB	Output is correct
14	Correct	72 ms	60152 KB	Output is correct
15	Correct	79 ms	60588 KB	Output is correct
16	Correct	90 ms	60900 KB	Output is correct
17	Correct	119 ms	61408 KB	Output is correct
18	Correct	136 ms	61408 KB	Output is correct
19	Correct	127 ms	61408 KB	Output is correct
20	Correct	110 ms	61408 KB	Output is correct
21	Correct	104 ms	61408 KB	Output is correct
22	Correct	89 ms	61408 KB	Output is correct
23	Correct	88 ms	61408 KB	Output is correct
24	Correct	89 ms	61408 KB	Output is correct
25	Correct	93 ms	61448 KB	Output is correct
26	Correct	122 ms	61448 KB	Output is correct
27	Correct	106 ms	61448 KB	Output is correct
28	Correct	98 ms	61448 KB	Output is correct
29	Correct	151 ms	61492 KB	Output is correct
30	Runtime error	206 ms	126064 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Halted	0 ms	0 KB	-

답안 #52209

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