답안 #52208 :: oj.uz

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

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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

void pst_insert(ll p, ll s, ll e, ll v)
{
	T[p].v ++;
	
	if(s == e) return;
	
	ll 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);
	}
}

ll pst_query(ll p, ll s, ll e, ll l, ll r)
{
	if(!p || r < s || e < l) return 0;
	if(l <= s && e <= r) return T[p].v;
	
	ll 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(ll p,ll 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]);
	}
}

ll max_idx(ll l,ll r)
{
	ll 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()
{
	ll i,l,r,p,x;
	
	scanf("%lld%lld",&n,&k);
	
	for(i=0;i<n;i++){
		scanf("%lld%lld",A+i,B+i);
	}
	
	for(i=0;i<k;i++){
		scanf("%lld",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 'll max_idx(ll, ll)':
fortune_telling2.cpp:63:5: warning: operation on 'l' may be undefined [-Wsequence-point]
   l = ++l >> 1;
   ~~^~~~~~~~~~
fortune_telling2.cpp:64:5: warning: operation on 'r' may be undefined [-Wsequence-point]
   r = --r >> 1;
   ~~^~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",A+i,B+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",K+i);
   ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	99 ms	119160 KB	Output is correct
2	Correct	100 ms	119160 KB	Output is correct
3	Correct	110 ms	119260 KB	Output is correct
4	Correct	106 ms	119272 KB	Output is correct
5	Correct	103 ms	119272 KB	Output is correct
6	Correct	98 ms	119272 KB	Output is correct
7	Correct	109 ms	119272 KB	Output is correct
8	Correct	112 ms	119272 KB	Output is correct
9	Correct	105 ms	119400 KB	Output is correct
10	Correct	109 ms	119440 KB	Output is correct
11	Correct	101 ms	119440 KB	Output is correct
12	Correct	106 ms	119440 KB	Output is correct
13	Correct	114 ms	119440 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	99 ms	119160 KB	Output is correct
2	Correct	100 ms	119160 KB	Output is correct
3	Correct	110 ms	119260 KB	Output is correct
4	Correct	106 ms	119272 KB	Output is correct
5	Correct	103 ms	119272 KB	Output is correct
6	Correct	98 ms	119272 KB	Output is correct
7	Correct	109 ms	119272 KB	Output is correct
8	Correct	112 ms	119272 KB	Output is correct
9	Correct	105 ms	119400 KB	Output is correct
10	Correct	109 ms	119440 KB	Output is correct
11	Correct	101 ms	119440 KB	Output is correct
12	Correct	106 ms	119440 KB	Output is correct
13	Correct	114 ms	119440 KB	Output is correct
14	Correct	121 ms	120340 KB	Output is correct
15	Correct	141 ms	121600 KB	Output is correct
16	Correct	161 ms	122820 KB	Output is correct
17	Correct	185 ms	124988 KB	Output is correct
18	Correct	197 ms	125216 KB	Output is correct
19	Correct	195 ms	125248 KB	Output is correct
20	Correct	177 ms	125256 KB	Output is correct
21	Correct	168 ms	125332 KB	Output is correct
22	Correct	161 ms	125332 KB	Output is correct
23	Correct	159 ms	125332 KB	Output is correct
24	Correct	159 ms	125332 KB	Output is correct
25	Correct	155 ms	125332 KB	Output is correct
26	Correct	156 ms	125332 KB	Output is correct
27	Correct	180 ms	125332 KB	Output is correct
28	Correct	179 ms	125332 KB	Output is correct
29	Correct	214 ms	125332 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	99 ms	119160 KB	Output is correct
2	Correct	100 ms	119160 KB	Output is correct
3	Correct	110 ms	119260 KB	Output is correct
4	Correct	106 ms	119272 KB	Output is correct
5	Correct	103 ms	119272 KB	Output is correct
6	Correct	98 ms	119272 KB	Output is correct
7	Correct	109 ms	119272 KB	Output is correct
8	Correct	112 ms	119272 KB	Output is correct
9	Correct	105 ms	119400 KB	Output is correct
10	Correct	109 ms	119440 KB	Output is correct
11	Correct	101 ms	119440 KB	Output is correct
12	Correct	106 ms	119440 KB	Output is correct
13	Correct	114 ms	119440 KB	Output is correct
14	Correct	121 ms	120340 KB	Output is correct
15	Correct	141 ms	121600 KB	Output is correct
16	Correct	161 ms	122820 KB	Output is correct
17	Correct	185 ms	124988 KB	Output is correct
18	Correct	197 ms	125216 KB	Output is correct
19	Correct	195 ms	125248 KB	Output is correct
20	Correct	177 ms	125256 KB	Output is correct
21	Correct	168 ms	125332 KB	Output is correct
22	Correct	161 ms	125332 KB	Output is correct
23	Correct	159 ms	125332 KB	Output is correct
24	Correct	159 ms	125332 KB	Output is correct
25	Correct	155 ms	125332 KB	Output is correct
26	Correct	156 ms	125332 KB	Output is correct
27	Correct	180 ms	125332 KB	Output is correct
28	Correct	179 ms	125332 KB	Output is correct
29	Correct	214 ms	125332 KB	Output is correct
30	Runtime error	379 ms	254468 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Halted	0 ms	0 KB	-

답안 #52208

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