Submission #62001

#	Time	Username	Problem	Language	Result	Execution time	Memory
62001		mohammedehab2002	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	0 / 100	43 ms	524 KiB

fortune_telling2

#include <iostream>
#include <algorithm>
using namespace std;
#define BU 450
pair<int,int> p[200005];
int lim[200005],lazy[800005];
bool cmp(pair<int,int> a,pair<int,int> b)
{
	return (a.second<b.second);
}
int merge(int x,int y)
{
	if (!y)
	return x;
	if (!x)
	return y;
	if (y==-1)
	return 3-x;
	return y;
}
void update(int node,int st,int en,int l,int r,int f)
{
	if (st!=en)
	{
		lazy[2*node]=merge(lazy[2*node],lazy[node]);
		lazy[2*node+1]=merge(lazy[2*node+1],lazy[node]);
		lazy[node]=0;
	}
	if (en<l || st>r || r<l)
	return;
	if (l<=st && en<=r)
	{
		lazy[node]=merge(lazy[node],f);
		return;
	}
	int mid=(st+en)/2;
	update(2*node,st,mid,l,r,f);
	update(2*node+1,mid+1,en,l,r,f);
}
long long query(int node,int st,int en,int idx)
{
	if (st!=en)
	{
		lazy[2*node]=merge(lazy[2*node],lazy[node]);
		lazy[2*node+1]=merge(lazy[2*node+1],lazy[node]);
		lazy[node]=0;
	}
	if (st==en)
	return lazy[node];
	else
	{
		int mid=(st+en)/2;
		if (st<=idx && idx<=mid)
		return query(2*node,st,mid,idx);
		return query(2*node+1,mid+1,en,idx);
	}
}
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i=0;i<n;i++)
	{
		scanf("%d%d",&p[i].first,&p[i].second);
		update(1,0,n-1,i,i,1);
	}
	sort(p,p+n);
	for (int i=0;i<n;i+=BU)
	lim[i]=p[min(i+BU,n)-1].first;
	for (int i=0;i<n;i+=BU)
	sort(p,p+min(BU,n-i),cmp);
	while (k--)
	{
		int x;
		scanf("%d",&x);
		for (int i=0;i<n;i+=BU)
		{
			if (lim[i]>x)
			{
				for (int j=i;j<min(i+BU,n);j++)
				{
					int tmp=query(1,0,n-1,j);
					if ((tmp==1 && p[j].first<=x) || (tmp==2 && p[j].second<=x))
					update(1,0,n-1,j,j,-1);
				}
				break;
			}
			int st=i,en=min(i+BU,n)-1;
			while (st!=en)
			{
				int mid=(st+en+1)/2;
				if (p[mid].second<=x)
				st=mid;
				else
				en=mid-1;
			}
			update(1,0,n-1,i,st,-1);
			update(1,0,n-1,st+1,min(i+BU,n)-1,2);
		}
	}
	long long ans=0;
	for (int i=0;i<n;i++)
	{
		if (query(1,0,n-1,i)==1)
		ans+=p[i].first;
		else
		ans+=p[i].second;
	}
	printf("%lld",ans);
}

Compilation message (stderr)

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

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65