| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 339054 |
2020-12-24T13:44:48 Z |
ogibogi2004 |
Boat (APIO16_boat) |
C++14 |
|
13 ms |
8812 KB |
#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;
}
Compilation message
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++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
8812 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
8812 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
8812 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
8812 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
