oj.uz

Submission #52208

# Submission time Handle Problem Language Result Execution time Memory
52208 2018-06-25T04:56:08 Z 김세빈(#1347) Fortune Telling 2 (JOI14_fortune_telling2) C++11
35 / 100
 379 ms 254468 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -