Submission #88943

#	Time	Username	Problem	Language	Result	Execution time	Memory
88943		ckodser	Boat (APIO16_boat)	C++14	0 / 100	200 ms	32224 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=400;///////////////////////// WARNINGGGGGG
const ll mod=1e9+7;

ll fac[maxm];
ll rfac[maxm];
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;
}


class black_box{
	public:
		void add_queri(int a){
			que.pb(a);
		}
		ll get_top(){
			ll ans=0;
			ll doo=0;
			for(ll i=(ll)que.size()-1;i>=0;i--){
				ll v=que[i];
				if(v==inf){
					doo++;
				}else{
					ans+=(v*find_tas(doo+1))%mod;
					if(ans>=mod)ans-=mod;
				}
			}
			return ans;
		}
		void set_tol(ll x){
			tol=x;
		}
	private:
		vector<ll> que;
		ll tol;
		ll find_tas(ll doo){
			return ent(tol+doo-1,doo);
		}
};

vector<ll> vecx;
ll a[maxn];
ll b[maxn];
black_box c[maxn];

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


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++){
		c[i].set_tol(vecx[i+1]-vecx[i]);
	}
	updatejam(0,inf,1);
	for(ll i=1;i<=n;i++){
		ll last=get_val(b[i]);
		updatecool(a[i],b[i]+1);
		updatejam(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:129: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)':
boat.cpp:137: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:178: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