oj.uz

Submission #151231

# Submission time Handle Problem Language Result Execution time Memory
151231 2019-09-02T09:37:51 Z TadijaSebez Fortune Telling 2 (JOI14_fortune_telling2) C++11
100 / 100
 600 ms 65128 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=200050;
const int M=20*N;
int ls[M],rs[M],tsz,sz[M],root[N];
void Set(int p, int &c, int ss, int se, int qi)
{
	c=++tsz;ls[c]=ls[p];rs[c]=rs[p];sz[c]=sz[p]+1;
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi);
	else Set(rs[p],rs[c],mid+1,se,qi);
}
int Get(int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe) return 0;
	if(qs<=ss && qe>=se) return sz[c];
	int mid=ss+se>>1;
	return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
int Last(int p, int c, int ss, int se)
{
	if(ss==se) return sz[c]-sz[p]>0?ss:-1;
	int mid=ss+se>>1;
	if(sz[rs[c]]-sz[rs[p]]>0) return Last(rs[p],rs[c],mid+1,se);
	else return Last(ls[p],ls[c],ss,mid);
}
int n,k,a[N],b[N],t[N],m;
vector<int> id,Qs[N];
int Get(int x){ return lower_bound(id.begin(),id.end(),x)-id.begin()+1;}
int main()
{
	scanf("%i %i",&n,&k);
	for(int i=1;i<=n;i++) scanf("%i %i",&a[i],&b[i]);
	for(int i=1;i<=k;i++) scanf("%i",&t[i]),id.pb(t[i]);
	sort(id.begin(),id.end());
	id.erase(unique(id.begin(),id.end()),id.end());
	for(int i=1;i<=k;i++) Qs[Get(t[i])].pb(i);
	m=id.size();
	for(int i=m;i>=1;i--)
	{
		root[i]=root[i+1];
		for(int pos:Qs[i]) Set(root[i],root[i],1,k,pos);
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		int mn=min(a[i],b[i]);
		int mx=max(a[i],b[i]);
		int lst=Last(root[Get(mx)],root[Get(mn)],1,k);
		int cnt;
		if(lst==-1) cnt=Get(root[Get(mx)],1,k,1,k);
		else cnt=Get(root[Get(mx)],1,k,lst+1,k);
        int x=a[i]==mn?0:1;
        if(lst!=-1) x=1;
        x^=cnt&1;
        if(x==0) ans+=mn;
        else ans+=mx;
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'void Set(int, int&, int, int, int)':
fortune_telling2.cpp:12:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
fortune_telling2.cpp: In function 'int Get(int, int, int, int, int)':
fortune_telling2.cpp:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
fortune_telling2.cpp: In function 'int Last(int, int, int, int)':
fortune_telling2.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:36:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&a[i],&b[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:37:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=k;i++) scanf("%i",&t[i]),id.pb(t[i]);
                        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 7 ms 5244 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 8 ms 5240 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 7 ms 5240 KB Output is correct
8 Correct 7 ms 5212 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 7 ms 5240 KB Output is correct
11 Correct 9 ms 5240 KB Output is correct
12 Correct 7 ms 5240 KB Output is correct
13 Correct 7 ms 5240 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 7 ms 5244 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 8 ms 5240 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 7 ms 5240 KB Output is correct
8 Correct 7 ms 5212 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 7 ms 5240 KB Output is correct
11 Correct 9 ms 5240 KB Output is correct
12 Correct 7 ms 5240 KB Output is correct
13 Correct 7 ms 5240 KB Output is correct
14 Correct 22 ms 7672 KB Output is correct
15 Correct 39 ms 10328 KB Output is correct
16 Correct 60 ms 13048 KB Output is correct
17 Correct 81 ms 15916 KB Output is correct
18 Correct 80 ms 15988 KB Output is correct
19 Correct 81 ms 15932 KB Output is correct
20 Correct 86 ms 15988 KB Output is correct
21 Correct 72 ms 15948 KB Output is correct
22 Correct 57 ms 15220 KB Output is correct
23 Correct 57 ms 15092 KB Output is correct
24 Correct 59 ms 14964 KB Output is correct
25 Correct 56 ms 15348 KB Output is correct
26 Correct 75 ms 15860 KB Output is correct
27 Correct 83 ms 16040 KB Output is correct
28 Correct 75 ms 15988 KB Output is correct
29 Correct 92 ms 16004 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 7 ms 5244 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 8 ms 5240 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 7 ms 5240 KB Output is correct
8 Correct 7 ms 5212 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 7 ms 5240 KB Output is correct
11 Correct 9 ms 5240 KB Output is correct
12 Correct 7 ms 5240 KB Output is correct
13 Correct 7 ms 5240 KB Output is correct
14 Correct 22 ms 7672 KB Output is correct
15 Correct 39 ms 10328 KB Output is correct
16 Correct 60 ms 13048 KB Output is correct
17 Correct 81 ms 15916 KB Output is correct
18 Correct 80 ms 15988 KB Output is correct
19 Correct 81 ms 15932 KB Output is correct
20 Correct 86 ms 15988 KB Output is correct
21 Correct 72 ms 15948 KB Output is correct
22 Correct 57 ms 15220 KB Output is correct
23 Correct 57 ms 15092 KB Output is correct
24 Correct 59 ms 14964 KB Output is correct
25 Correct 56 ms 15348 KB Output is correct
26 Correct 75 ms 15860 KB Output is correct
27 Correct 83 ms 16040 KB Output is correct
28 Correct 75 ms 15988 KB Output is correct
29 Correct 92 ms 16004 KB Output is correct
30 Correct 303 ms 60032 KB Output is correct
31 Correct 345 ms 60988 KB Output is correct
32 Correct 398 ms 62312 KB Output is correct
33 Correct 590 ms 65096 KB Output is correct
34 Correct 263 ms 59408 KB Output is correct
35 Correct 581 ms 65004 KB Output is correct
36 Correct 551 ms 65128 KB Output is correct
37 Correct 569 ms 65012 KB Output is correct
38 Correct 568 ms 65000 KB Output is correct
39 Correct 582 ms 64992 KB Output is correct
40 Correct 415 ms 64796 KB Output is correct
41 Correct 600 ms 65000 KB Output is correct
42 Correct 577 ms 64928 KB Output is correct
43 Correct 318 ms 64204 KB Output is correct
44 Correct 335 ms 64368 KB Output is correct
45 Correct 331 ms 64272 KB Output is correct
46 Correct 339 ms 61160 KB Output is correct
47 Correct 344 ms 60396 KB Output is correct
48 Correct 478 ms 65104 KB Output is correct
49 Correct 450 ms 64924 KB Output is correct