답안 #52213 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52213	2018-06-25T04:59:08 Z	김세빈(#1347)	운세 보기 2 (JOI14_fortune_telling2)	C++11	100 / 100	610 ms	66164 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[606060];
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	50 ms	59640 KB	Output is correct
3	Correct	50 ms	59752 KB	Output is correct
4	Correct	50 ms	59860 KB	Output is correct
5	Correct	60 ms	59916 KB	Output is correct
6	Correct	53 ms	59916 KB	Output is correct
7	Correct	49 ms	59916 KB	Output is correct
8	Correct	48 ms	59916 KB	Output is correct
9	Correct	49 ms	59916 KB	Output is correct
10	Correct	50 ms	59916 KB	Output is correct
11	Correct	58 ms	59916 KB	Output is correct
12	Correct	49 ms	59916 KB	Output is correct
13	Correct	55 ms	59988 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	59640 KB	Output is correct
2	Correct	50 ms	59640 KB	Output is correct
3	Correct	50 ms	59752 KB	Output is correct
4	Correct	50 ms	59860 KB	Output is correct
5	Correct	60 ms	59916 KB	Output is correct
6	Correct	53 ms	59916 KB	Output is correct
7	Correct	49 ms	59916 KB	Output is correct
8	Correct	48 ms	59916 KB	Output is correct
9	Correct	49 ms	59916 KB	Output is correct
10	Correct	50 ms	59916 KB	Output is correct
11	Correct	58 ms	59916 KB	Output is correct
12	Correct	49 ms	59916 KB	Output is correct
13	Correct	55 ms	59988 KB	Output is correct
14	Correct	62 ms	60268 KB	Output is correct
15	Correct	78 ms	60764 KB	Output is correct
16	Correct	90 ms	60908 KB	Output is correct
17	Correct	108 ms	61288 KB	Output is correct
18	Correct	126 ms	61324 KB	Output is correct
19	Correct	110 ms	61324 KB	Output is correct
20	Correct	112 ms	61324 KB	Output is correct
21	Correct	105 ms	61324 KB	Output is correct
22	Correct	107 ms	61324 KB	Output is correct
23	Correct	119 ms	61324 KB	Output is correct
24	Correct	106 ms	61324 KB	Output is correct
25	Correct	94 ms	61324 KB	Output is correct
26	Correct	101 ms	61324 KB	Output is correct
27	Correct	137 ms	61324 KB	Output is correct
28	Correct	104 ms	61324 KB	Output is correct
29	Correct	147 ms	61324 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	59640 KB	Output is correct
2	Correct	50 ms	59640 KB	Output is correct
3	Correct	50 ms	59752 KB	Output is correct
4	Correct	50 ms	59860 KB	Output is correct
5	Correct	60 ms	59916 KB	Output is correct
6	Correct	53 ms	59916 KB	Output is correct
7	Correct	49 ms	59916 KB	Output is correct
8	Correct	48 ms	59916 KB	Output is correct
9	Correct	49 ms	59916 KB	Output is correct
10	Correct	50 ms	59916 KB	Output is correct
11	Correct	58 ms	59916 KB	Output is correct
12	Correct	49 ms	59916 KB	Output is correct
13	Correct	55 ms	59988 KB	Output is correct
14	Correct	62 ms	60268 KB	Output is correct
15	Correct	78 ms	60764 KB	Output is correct
16	Correct	90 ms	60908 KB	Output is correct
17	Correct	108 ms	61288 KB	Output is correct
18	Correct	126 ms	61324 KB	Output is correct
19	Correct	110 ms	61324 KB	Output is correct
20	Correct	112 ms	61324 KB	Output is correct
21	Correct	105 ms	61324 KB	Output is correct
22	Correct	107 ms	61324 KB	Output is correct
23	Correct	119 ms	61324 KB	Output is correct
24	Correct	106 ms	61324 KB	Output is correct
25	Correct	94 ms	61324 KB	Output is correct
26	Correct	101 ms	61324 KB	Output is correct
27	Correct	137 ms	61324 KB	Output is correct
28	Correct	104 ms	61324 KB	Output is correct
29	Correct	147 ms	61324 KB	Output is correct
30	Correct	284 ms	64516 KB	Output is correct
31	Correct	328 ms	64952 KB	Output is correct
32	Correct	445 ms	65280 KB	Output is correct
33	Correct	572 ms	65964 KB	Output is correct
34	Correct	328 ms	65964 KB	Output is correct
35	Correct	566 ms	66076 KB	Output is correct
36	Correct	519 ms	66076 KB	Output is correct
37	Correct	607 ms	66144 KB	Output is correct
38	Correct	610 ms	66144 KB	Output is correct
39	Correct	566 ms	66144 KB	Output is correct
40	Correct	493 ms	66144 KB	Output is correct
41	Correct	488 ms	66144 KB	Output is correct
42	Correct	600 ms	66144 KB	Output is correct
43	Correct	368 ms	66144 KB	Output is correct
44	Correct	346 ms	66144 KB	Output is correct
45	Correct	371 ms	66144 KB	Output is correct
46	Correct	341 ms	66144 KB	Output is correct
47	Correct	362 ms	66144 KB	Output is correct
48	Correct	537 ms	66144 KB	Output is correct
49	Correct	414 ms	66164 KB	Output is correct

답안 #52213

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 65.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
65.0 / 65.0