Submission #88946

#	Time	Username	Problem	Language	Result	Execution time	Memory
88946		ckodser	Boat (APIO16_boat)	C++14	0 / 100	179 ms	16120 KiB

boat

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll> 
#define move movEe
using namespace :: std;

const ll maxn=1100;
const ll maxm=1e6+200;
const ll inf=1e9+400;
const ll mod=1e9+7;

ll fac[maxm];
ll rfac[maxm];

vector<ll> que[maxn];
ll tol[maxn];

ll poww(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1){
			ans=(ans*a)%mod;
		}
		a=(a*a)%mod;
		b/=2;
	}
	return ans;
}
inline ll ent(ll n,ll k){
	return (((fac[n]*rfac[k])%mod)*rfac[n-k])%mod;
}
inline void ok(ll &a){
	if(a>=mod)a-=mod;
}

ll get_top(ll v){
	ll ans=0;
	ll doo=0;
	for(ll i=(ll)que[v].size()-1;i>=0;i--){
		ll u=que[v][i];
		if(u==inf){
			doo++;
		}else{
			ans+=(u*ent(tol[v]+doo,doo+1))%mod;
			ok(ans);
		}
	}
	return ans;
}
vector<ll> vecx;
ll a[maxn];
ll b[maxn];


void updatejam(ll l,ll r,ll v){
	for(ll i=0;i<vecx.size();i++){
		if(l<=vecx[i] && vecx[i]<r){
			que[i].pb(v);
		}
	}
}
void updatecool(ll l,ll r,ll x){
	ll last=x;
	for(ll i=0;i<vecx.size();i++){
		if(l<=vecx[i] && vecx[i]<r){
			que[i].pb(inf);
			if(last!=0){
				que[i].pb(last);
			}
			last=get_top(i);
		}
	}
}
ll get_val(ll a){
	ll v=lower_bound(vecx.begin(),vecx.end(),a+1)-vecx.begin()-1;
	return get_top(v);
}


int main(){
	fac[0]=1;
	rfac[0]=1;
	for(ll i=1;i<maxm;i++){
		fac[i]=(fac[i-1]*i)%mod;
		rfac[i]=poww(fac[i],mod-2);
	}

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	ll n;
	cin>>n;
	vecx.pb(0);
	vecx.pb(1);
	vecx.pb(inf);
	vecx.pb(inf-1);
	for(ll i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		vecx.pb(a[i]);
		vecx.pb(b[i]+1);
	}
	{
		sort(vecx.begin(),vecx.end());
		auto it=unique(vecx.begin(),vecx.end());
		vecx.resize(it-vecx.begin());
	}
	for(ll i=0;i+1<vecx.size();i++){
		tol[i]=(vecx[i+1]-vecx[i]);
	}
	cout<<1;
	return 0;
	updatejam(0,inf,1);
	for(ll i=1;i<=n;i++){
		ll last=get_val(b[i]);
		updatecool(a[i],b[i]+1,get_val(a[i]-1));
		ll neww=get_val(b[i]);
		updatejam(b[i]+1,inf,(neww-last+mod)%mod);
	}
	cout<<(get_val(inf-1)-1+mod)%mod;
}

Compilation message (stderr)

boat.cpp: In function 'void updatejam(long long int, long long int, long long int)':
boat.cpp:116:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<vecx.size();i++){
             ~^~~~~~~~~~~~
boat.cpp: In function 'void updatecool(long long int, long long int, long long int)':
boat.cpp:124:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<vecx.size();i++){
             ~^~~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:165:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i+1<vecx.size();i++){
             ~~~^~~~~~~~~~~~

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