답안 #62212 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62212	2018-07-27T21:03:12 Z	mohammedehab2002	운세 보기 2 (JOI14_fortune_telling2)	C++11	100 / 100	2755 ms	163212 KB

fortune_telling2

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
using namespace __gnu_pbds;
map<int,int> m;
vector<int> v[200005];
int a[200005],b[200005],mn[200005],mx[200005],q[200005],Tree[3000005];
tree<int,null_type,greater_equal<int>,rb_tree_tag,tree_order_statistics_node_update> t;
void update(int node,int st,int en,int idx,int val)
{
	if (st==en)
	Tree[node]=val;
	else
	{
		int mid=(st+en)/2;
		if (st<=idx && idx<=mid)
		update(2*node,st,mid,idx,val);
		else
		update(2*node+1,mid+1,en,idx,val);
		Tree[node]=max(Tree[2*node],Tree[2*node+1]);
	}
}
int query(int node,int st,int en,int l,int r)
{
	if (en<l || st>r || r<l)
	return -1;
	if (l<=st && en<=r)
	return Tree[node];
	int mid=(st+en)/2;
	return max(query(2*node,st,mid,l,r),query(2*node+1,mid+1,en,l,r));
}
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i=0;i<n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		m[a[i]];
		m[b[i]];
		mn[i]=min(a[i],b[i]);
		mx[i]=max(a[i],b[i]);
	}
	for (int i=0;i<k;i++)
	{
		scanf("%d",&q[i]);
		m[q[i]];
	}
	int cnt=0;
	for (auto &i:m)
	i.second=cnt++;
	memset(Tree,-1,sizeof(Tree));
	for (int i=0;i<k;i++)
	update(1,0,2*n+k,m[q[i]],i);
	for (int i=0;i<n;i++)
	v[query(1,0,2*n+k,m[mn[i]],m[mx[i]]-1)+1].push_back(i);
	long long ans=0;
	for (int i=k;i>=0;i--)
	{
		if (i!=k)
		t.insert(q[i]);
		for (int j:v[i])
		{
			int cnt=t.order_of_key(mx[j]-1);
			if (!i)
			cnt+=(mn[j]==a[j]);
			if (cnt%2)
			ans+=mn[j];
			else
			ans+=mx[j];
		}
	}
	printf("%lld",ans);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:39: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:42: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:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	16888 KB	Output is correct
2	Correct	20 ms	17008 KB	Output is correct
3	Correct	20 ms	17096 KB	Output is correct
4	Correct	21 ms	17164 KB	Output is correct
5	Correct	23 ms	17196 KB	Output is correct
6	Correct	23 ms	17228 KB	Output is correct
7	Correct	19 ms	17388 KB	Output is correct
8	Correct	23 ms	17388 KB	Output is correct
9	Correct	20 ms	17400 KB	Output is correct
10	Correct	19 ms	17400 KB	Output is correct
11	Correct	18 ms	17436 KB	Output is correct
12	Correct	20 ms	17544 KB	Output is correct
13	Correct	20 ms	17544 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	16888 KB	Output is correct
2	Correct	20 ms	17008 KB	Output is correct
3	Correct	20 ms	17096 KB	Output is correct
4	Correct	21 ms	17164 KB	Output is correct
5	Correct	23 ms	17196 KB	Output is correct
6	Correct	23 ms	17228 KB	Output is correct
7	Correct	19 ms	17388 KB	Output is correct
8	Correct	23 ms	17388 KB	Output is correct
9	Correct	20 ms	17400 KB	Output is correct
10	Correct	19 ms	17400 KB	Output is correct
11	Correct	18 ms	17436 KB	Output is correct
12	Correct	20 ms	17544 KB	Output is correct
13	Correct	20 ms	17544 KB	Output is correct
14	Correct	73 ms	19848 KB	Output is correct
15	Correct	150 ms	22508 KB	Output is correct
16	Correct	289 ms	25436 KB	Output is correct
17	Correct	375 ms	28808 KB	Output is correct
18	Correct	411 ms	30016 KB	Output is correct
19	Correct	344 ms	31276 KB	Output is correct
20	Correct	352 ms	32364 KB	Output is correct
21	Correct	312 ms	33448 KB	Output is correct
22	Correct	184 ms	33448 KB	Output is correct
23	Correct	191 ms	33448 KB	Output is correct
24	Correct	168 ms	33448 KB	Output is correct
25	Correct	245 ms	34892 KB	Output is correct
26	Correct	224 ms	35024 KB	Output is correct
27	Correct	220 ms	36640 KB	Output is correct
28	Correct	225 ms	37916 KB	Output is correct
29	Correct	338 ms	40136 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	16888 KB	Output is correct
2	Correct	20 ms	17008 KB	Output is correct
3	Correct	20 ms	17096 KB	Output is correct
4	Correct	21 ms	17164 KB	Output is correct
5	Correct	23 ms	17196 KB	Output is correct
6	Correct	23 ms	17228 KB	Output is correct
7	Correct	19 ms	17388 KB	Output is correct
8	Correct	23 ms	17388 KB	Output is correct
9	Correct	20 ms	17400 KB	Output is correct
10	Correct	19 ms	17400 KB	Output is correct
11	Correct	18 ms	17436 KB	Output is correct
12	Correct	20 ms	17544 KB	Output is correct
13	Correct	20 ms	17544 KB	Output is correct
14	Correct	73 ms	19848 KB	Output is correct
15	Correct	150 ms	22508 KB	Output is correct
16	Correct	289 ms	25436 KB	Output is correct
17	Correct	375 ms	28808 KB	Output is correct
18	Correct	411 ms	30016 KB	Output is correct
19	Correct	344 ms	31276 KB	Output is correct
20	Correct	352 ms	32364 KB	Output is correct
21	Correct	312 ms	33448 KB	Output is correct
22	Correct	184 ms	33448 KB	Output is correct
23	Correct	191 ms	33448 KB	Output is correct
24	Correct	168 ms	33448 KB	Output is correct
25	Correct	245 ms	34892 KB	Output is correct
26	Correct	224 ms	35024 KB	Output is correct
27	Correct	220 ms	36640 KB	Output is correct
28	Correct	225 ms	37916 KB	Output is correct
29	Correct	338 ms	40136 KB	Output is correct
30	Correct	962 ms	55528 KB	Output is correct
31	Correct	1350 ms	62924 KB	Output is correct
32	Correct	1773 ms	72636 KB	Output is correct
33	Correct	2719 ms	89728 KB	Output is correct
34	Correct	785 ms	89728 KB	Output is correct
35	Correct	2755 ms	97412 KB	Output is correct
36	Correct	2676 ms	103444 KB	Output is correct
37	Correct	2556 ms	108844 KB	Output is correct
38	Correct	2750 ms	114880 KB	Output is correct
39	Correct	2659 ms	120996 KB	Output is correct
40	Correct	2357 ms	126196 KB	Output is correct
41	Correct	2695 ms	132020 KB	Output is correct
42	Correct	2662 ms	138008 KB	Output is correct
43	Correct	1503 ms	142864 KB	Output is correct
44	Correct	1355 ms	148084 KB	Output is correct
45	Correct	1248 ms	153092 KB	Output is correct
46	Correct	1458 ms	153092 KB	Output is correct
47	Correct	1105 ms	153092 KB	Output is correct
48	Correct	1598 ms	157472 KB	Output is correct
49	Correct	1577 ms	163212 KB	Output is correct

답안 #62212

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