Submission #151231

#	Time	Username	Problem	Language	Result	Execution time	Memory
151231		TadijaSebez	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	600 ms	65128 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65