제출 #62047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62047		mohammedehab2002	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	4 / 100	3016 ms	1252 KiB

fortune_telling2

#include <iostream>
#include <algorithm>
using namespace std;
#define BU 450
pair<pair<int,int>,bool> p[200005];
int lim[200005],lazy[800005];
bool cmp(pair<pair<int,int>,bool> a,pair<pair<int,int>,bool> b)
{
	return (a.first.second<b.first.second);
}
int merge(int x,int y)
{
	if (!y)
	return x;
	if (!x)
	return y;
	if (y==-1)
	{
		if (x==-1)
		return 0;
		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.first,&p[i].first.second);
		p[i].second=0;
		if (p[i].first.first>p[i].first.second)
		{
			swap(p[i].first.first,p[i].first.second);
			p[i].second=1;
		}
	}
	sort(p,p+n);
	for (int i=0;i<n;i+=BU)
	lim[i]=p[min(i+BU,n)-1].first.first;
	for (int i=0;i<n;i+=BU)
	sort(p+i,p+i+min(BU,n-i),cmp);
	for (int i=0;i<n;i++)
	update(1,0,n-1,i,i,(int)p[i].second+1);
	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.first<=x) || (tmp==2 && p[j].first.second<=x))
					update(1,0,n-1,j,j,-1);
				}
				break;
			}
			int st=i-1,en=min(i+BU,n)-1;
			while (st!=en)
			{
				int mid=(st+en+1)/2;
				if (p[mid].first.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.first;
		else
		ans+=p[i].first.second;
	}
	printf("%lld",ans);
}

컴파일 시 표준 에러 (stderr) 메시지

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

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