oj.uz

Submission #68312

# Submission time Handle Problem Language Result Execution time Memory
68312 2018-08-16T15:37:03 Z thebes Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 1779 ms 135104 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MN = 200005;
struct pii{ll f, s, l;}a[MN];
ll st[3*MN], q[MN], N, K, M, i, j, n, bit[MN];
long long ans; map<int,int> p;

bool cmp(pii i,pii j){return(i.l<j.l);}
ll qu(ll p){ll r=0;for(;p>0;p-=p&(-p))r+=bit[p]; return r;}
void up(ll p){for(;p<=M;p+=p&(-p))bit[p]++;}

void upd(ll i,ll s,ll e,ll ind, ll k){
	if(s != e){
		if((s+e)/2 < ind) upd(2*i+1,(s+e)/2+1,e,ind,k);
		else upd(2*i,s,(s+e)/2,ind,k);
		st[i] = max(st[2*i],st[2*i+1]);
	}
	else st[i] = k;
}

ll rmq(ll i,ll s,ll e,ll ss,ll se){
	if(ss > se) return -1;
	if(s >= ss && e <= se) return st[i];
	else if((s+e)/2 < ss) return rmq(2*i+1,(s+e)/2+1,e,ss,se);
	else if((s+e)/2 >= se) return rmq(2*i,s,(s+e)/2,ss,se);
	else return max(rmq(2*i+1,(s+e)/2+1,e,ss,se),rmq(2*i,s,(s+e)/2,ss,se));
}

int main(){
	for(scanf("%lld%lld",&N,&K),i=1;i<=N;i++)
		scanf("%lld%lld",&a[i].f,&a[i].s);
	for(i=1;i<=K;i++){
		scanf("%lld",&q[i]);
		p[q[i]]=0;
	}
	for(auto v=p.begin();v!=p.end();v++) v->second = ++n;
	M = p.size();
	for(i=1;i<=K;i++)
		upd(1,1,M,p[q[i]],i);
	for(i=1;i<=N;i++){
		ll l, r;
		auto it = p.lower_bound(max(a[i].f,a[i].s)); --it;
		r = (it==p.end())? -1:it->second;
		it = p.lower_bound(min(a[i].f,a[i].s));
		l = (it==p.end())? 1<<30:it->second;
		a[i].l = rmq(1,1,M,l,r);
	}
	sort(a+1, a+N+1, cmp);
	for(i=N,j=K;i>=1&&a[i].l!=-1;i--){
		while(j>a[i].l){up(p[q[j]]);j--;}
		if(a[i].f < a[i].s) swap(a[i].f,a[i].s);
		auto tmp = p.lower_bound(a[i].f);
		ll ind = (tmp==p.end())? M:tmp->second-1;
		ll t = (qu(M)-qu(ind))%2;
		ans += (t)? a[i].s : a[i].f;
	}
	while(j > 0){up(p[q[j]]); j--;}
	for(;i>=1;i--){
		auto tmp = p.lower_bound(max(a[i].s,a[i].f));
		ll ind = (tmp==p.end())? M:tmp->second-1;
		ll t = (qu(M)-qu(ind))%2;
		ans += (t)? a[i].s : a[i].f;
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:32:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(scanf("%lld%lld",&N,&K),i=1;i<=N;i++)
      ~~~~~~~~~~~~~~~~~~~~~~~^~~~
fortune_telling2.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a[i].f,&a[i].s);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&q[i]);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 620 KB Output is correct
3 Correct 5 ms 644 KB Output is correct
4 Correct 5 ms 644 KB Output is correct
5 Correct 4 ms 704 KB Output is correct
6 Correct 4 ms 800 KB Output is correct
7 Correct 6 ms 832 KB Output is correct
8 Correct 6 ms 920 KB Output is correct
9 Correct 5 ms 956 KB Output is correct
10 Correct 4 ms 956 KB Output is correct
11 Correct 5 ms 988 KB Output is correct
12 Correct 7 ms 1020 KB Output is correct
13 Correct 5 ms 1180 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 620 KB Output is correct
3 Correct 5 ms 644 KB Output is correct
4 Correct 5 ms 644 KB Output is correct
5 Correct 4 ms 704 KB Output is correct
6 Correct 4 ms 800 KB Output is correct
7 Correct 6 ms 832 KB Output is correct
8 Correct 6 ms 920 KB Output is correct
9 Correct 5 ms 956 KB Output is correct
10 Correct 4 ms 956 KB Output is correct
11 Correct 5 ms 988 KB Output is correct
12 Correct 7 ms 1020 KB Output is correct
13 Correct 5 ms 1180 KB Output is correct
14 Correct 28 ms 2488 KB Output is correct
15 Correct 70 ms 4288 KB Output is correct
16 Correct 127 ms 5884 KB Output is correct
17 Correct 158 ms 8456 KB Output is correct
18 Correct 194 ms 9596 KB Output is correct
19 Correct 161 ms 10960 KB Output is correct
20 Correct 154 ms 11952 KB Output is correct
21 Correct 180 ms 13032 KB Output is correct
22 Correct 102 ms 13032 KB Output is correct
23 Correct 128 ms 13364 KB Output is correct
24 Correct 128 ms 14080 KB Output is correct
25 Correct 125 ms 15588 KB Output is correct
26 Correct 114 ms 16812 KB Output is correct
27 Correct 149 ms 18112 KB Output is correct
28 Correct 126 ms 19384 KB Output is correct
29 Correct 135 ms 20464 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 620 KB Output is correct
3 Correct 5 ms 644 KB Output is correct
4 Correct 5 ms 644 KB Output is correct
5 Correct 4 ms 704 KB Output is correct
6 Correct 4 ms 800 KB Output is correct
7 Correct 6 ms 832 KB Output is correct
8 Correct 6 ms 920 KB Output is correct
9 Correct 5 ms 956 KB Output is correct
10 Correct 4 ms 956 KB Output is correct
11 Correct 5 ms 988 KB Output is correct
12 Correct 7 ms 1020 KB Output is correct
13 Correct 5 ms 1180 KB Output is correct
14 Correct 28 ms 2488 KB Output is correct
15 Correct 70 ms 4288 KB Output is correct
16 Correct 127 ms 5884 KB Output is correct
17 Correct 158 ms 8456 KB Output is correct
18 Correct 194 ms 9596 KB Output is correct
19 Correct 161 ms 10960 KB Output is correct
20 Correct 154 ms 11952 KB Output is correct
21 Correct 180 ms 13032 KB Output is correct
22 Correct 102 ms 13032 KB Output is correct
23 Correct 128 ms 13364 KB Output is correct
24 Correct 128 ms 14080 KB Output is correct
25 Correct 125 ms 15588 KB Output is correct
26 Correct 114 ms 16812 KB Output is correct
27 Correct 149 ms 18112 KB Output is correct
28 Correct 126 ms 19384 KB Output is correct
29 Correct 135 ms 20464 KB Output is correct
30 Correct 801 ms 35112 KB Output is correct
31 Correct 967 ms 38864 KB Output is correct
32 Correct 1150 ms 44076 KB Output is correct
33 Correct 1406 ms 52028 KB Output is correct
34 Correct 681 ms 52028 KB Output is correct
35 Correct 1384 ms 59916 KB Output is correct
36 Correct 1494 ms 65568 KB Output is correct
37 Correct 1462 ms 71624 KB Output is correct
38 Correct 1304 ms 77228 KB Output is correct
39 Correct 1554 ms 83192 KB Output is correct
40 Correct 1135 ms 88644 KB Output is correct
41 Correct 1546 ms 94484 KB Output is correct
42 Correct 1779 ms 100316 KB Output is correct
43 Correct 962 ms 105540 KB Output is correct
44 Correct 849 ms 110752 KB Output is correct
45 Correct 1002 ms 115780 KB Output is correct
46 Correct 740 ms 116616 KB Output is correct
47 Correct 701 ms 117344 KB Output is correct
48 Correct 991 ms 129328 KB Output is correct
49 Correct 1039 ms 135104 KB Output is correct