제출 #339054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339054		ogibogi2004	Boat (APIO16_boat)	C++14	0 / 100	13 ms	8812 KiB

boat

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1e9+7;
const ll MAXN=512;
ll comb[MAXN][MAXN];
ll pref[MAXN][MAXN],a[MAXN],b[MAXN];
ll get_pref(ll x,ll y)
{
	if(x<0)return 0;
	if(y<0)return 0;
	return pref[x][y];
}
ll calc1(ll k,ll n)
{
	return (get_pref(n,k)-get_pref(n,k-1)+MOD)%MOD;
}
ll n;
struct chain
{
	ll l,r;
	vector<ll>k;
	ll calc()
	{
		ll ret=0;
		for(ll i=0;i<k.size();i++)
		{
			if(k[i]==0)continue;
			ret+=calc1(k.size()-i-1,r-l)*k[i];
			ret%=MOD;
		}
		return ret;
	}
	ll pth(ll p)
	{
		ll ret=0;
		for(ll i=0;i<k.size();i++)
		{
			ret+=comb[p][k.size()-i-1]*k[i];
			ret%=MOD;
		}
		return ret;
	}
	bool operator<(chain const& other)const
	{
		return l<other.l;
	}
};
set<chain>s;
void upd(ll l,ll r)
{
	vector<chain>to_remove;
	vector<chain>to_add;
	//cout<<1<<endl;
	for(set<chain>::iterator it=s.begin();it!=s.end();it++)
	{
		auto xd=(*it);
		if(xd.r<l)continue;
		if(xd.l>r)continue;
		if(xd.l>=l&&xd.r<=r)continue;
		to_remove.push_back(xd);
		chain xd1,xd2;
		xd1=xd;
		if(xd.l<l)
		{
			xd1.r=l-1;
			xd2=xd;
			xd2.l=l;
			xd2.k.back()=xd.pth(xd1.r-xd1.l+2);
		}
		else
		{
			xd1.r=r;
			xd2=xd;
			xd2.l=r+1;
			xd2.k.back()=xd.pth(xd1.r-xd1.l+2);
		}
		to_add.push_back(xd1);
		to_add.push_back(xd2);
	}
	//cout<<2<<endl;
	for(auto xd:to_remove)
	{
		s.erase(xd);
	}
	for(auto xd:to_add)
	{
		s.insert(xd);
	}
	//cout<<3<<endl;
	ll cur_sum=0,s1;
	to_remove.clear();
	to_add.clear();
	for(set<chain>::iterator it=s.begin();it!=s.end();it++)
	{
		auto xd=(*it);
		//cout<<"*\n";
		s1=xd.calc();
		//cout<<"**\n";
		if(xd.l>=l&&xd.r<=r)
		{
			to_remove.push_back(xd);
			xd.k.push_back(cur_sum);
			to_add.push_back(xd);
			//cout<<"&&"<<cur_sum<<endl;
		}
		//cout<<"***\n";
		cur_sum+=s1;
		cur_sum%=MOD;
	}
	for(auto xd:to_remove)s.erase(xd);
	for(auto xd:to_add)s.insert(xd);
	//cout<<4<<endl;
}
int main()
{
	comb[0][0]=1;
	for(ll i=0;i<MAXN;i++)
	{
		for(ll j=0;j<MAXN;j++)
		{
			if(i!=0)comb[i][j]+=comb[i-1][j];
			if(j!=0)comb[i][j]+=comb[i][j-1];
			comb[i][j]%=MOD;
			if(j>i)comb[i][j]=0;
			pref[i][j]=(get_pref(i-1,j)+get_pref(i,j-1)+comb[i][j]-get_pref(i-1,j-1)+4*MOD)%MOD;
		}
	}
	cin>>n;
	for(ll i=1;i<=n;i++)cin>>a[i]>>b[i];
	s.insert({0,0,{1}});
	s.insert({1,1000000000,{0}});
	for(ll i=1;i<=n;i++)
	{
		upd(a[i],b[i]);
	}
	/*for(auto xd:s)
	{
		cout<<xd.l<<" "<<xd.r<<":\n";
		for(int j=0;j<xd.k.size();j++)cout<<xd.k[j]<<" ";
		cout<<endl;
	}*/
	ll ans=0;
	for(auto xd:s)
	{
		ans+=xd.calc();
		ans%=MOD;
	}
	cout<<ans<<endl;
return 0;
}

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

boat.cpp: In member function 'long long int chain::calc()':
boat.cpp:26:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(ll i=0;i<k.size();i++)
      |              ~^~~~~~~~~
boat.cpp: In member function 'long long int chain::pth(long long int)':
boat.cpp:37:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(ll i=0;i<k.size();i++)
      |              ~^~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42