제출 #62212

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

fortune_telling2

#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);
}

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

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