답안 #68312 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68312	2018-08-16T15:37:03 Z	thebes	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	1779 ms	135104 KB

fortune_telling2

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #68312

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