oj.uz

Submission #62212

# Submission time Handle Problem Language Result Execution time Memory
62212 2018-07-27T21:03:12 Z mohammedehab2002 Fortune Telling 2 (JOI14_fortune_telling2) C++11
100 / 100
 2755 ms 163212 KB 
#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

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

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

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