제출 #389873

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

fortune_telling2

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

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

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

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