제출 #389860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389860		ogibogi2004	운세 보기 2 (JOI14_fortune_telling2)	C++14	0 / 100	7 ms	9804 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
const int MAXM=6e5+6;
const int INF=2e9;
map<int,int>mp;
set<int>xs;
int n,k;
int t[MAXN],a[MAXN],b[MAXN];
bool cmp(pair<int,int> p1,pair<int,int>p2)
{
	return make_pair(max(p1.first,p1.second),min(p1.first,p1.second))>make_pair(max(p2.first,p2.second),min(p2.first,p2.second));
}
vector<pair<int,int> >v;
struct segment_tree
{
	int tree[4*MAXM];
	void init()
	{
		memset(tree,0,sizeof(tree));
	}
	void update(int l,int r,int q,int idx,int val)
	{
		if(l>q)return;
		if(r<q)return;
		if(l==r)
		{
			tree[idx]=max(tree[idx],val);
			return;
		}
		int mid=(l+r)/2;
		update(l,mid,q,idx*2,val);
		update(mid+1,r,q,idx*2+1,val);
	}
	int query(int l,int r,int idx,int ql,int qr)
	{
		if(ql>qr)return 0;
		if(l>qr||r<ql)return 0;
		if(l>=ql&&r<=qr)return tree[idx];
		int mid=(l+r)/2;
		return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
	}
}ivan;
struct BIT
{
	int fen[MAXM];
	void update(int idx,int val)
	{
		idx++;
		for(;idx<MAXM;idx+=idx&(-idx))
		{
			fen[idx]+=val;
		}
	}
	int query(int idx)
	{
		idx++;
		int ret=0;
		for(;idx>0;idx-=idx&(-idx))
		{
			ret+=fen[idx];
		}
		return ret;
	}
	int query(int l,int r)
	{
		return query(r)-query(l-1);
	}
}vanka;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		xs.insert(a[i]);
		xs.insert(b[i]);
		v.push_back({a[i],b[i]});
	}
	sort(v.begin(),v.end(),cmp);
	for(int i=1;i<=k;i++)
	{
		cin>>t[i];
		xs.insert(t[i]);
	}
	xs.insert(INF);
	int cnt=0;
	for(auto xd:xs)
	{
		cnt++;
		mp[xd]=cnt;
	}
	vector<pair<int,int> >v1;
	ivan.init();
	int ans=0;
	for(int i=1;i<=k;i++)
	{
		v1.push_back({t[i],i});
		ivan.update(1,cnt,mp[t[i]],1,i);
	}
	sort(v1.begin(),v1.end());
	int r=v1.size()-1;
	for(int i=0;i<v.size();i++)
	{
		while(r>=0&&v1[r].first>=max(v[i].first,v[i].second))
		{
			//cout<<"*\n";
			vanka.update(v1[r].second,+1);
			r--;
		}
		int lastxd=ivan.query(1,cnt,1,mp[min(v[i].first,v[i].second)],mp[max(v[i].first,v[i].second)]-1);
		//cout<<lastxd<<endl;
		if(lastxd==0)
		{
			int f=vanka.query(1,k);
			//cout<<f<<endl;
			if(f%2==1)ans+=v[i].second;
			else ans+=v[i].first;
		}
		else
		{
			int f=vanka.query(lastxd+1,k);
			if(f%2==0)
			{
				ans+=max(v[i].first,v[i].second);
			}
			else
			{
				ans+=min(v[i].first,v[i].second);
			}
		}
		//cout<<v[i].first<<" "<<v[i].second<<" "<<ans<<endl;
	}
	cout<<ans<<endl;
return 0;
}

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

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:103:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for(int i=0;i<v.size();i++)
      |              ~^~~~~~~~~

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