oj.uz

Submission #88945

# Submission time Handle Problem Language Result Execution time Memory
88945 2018-12-10T06:38:20 Z ckodser Boat (APIO16_boat) C++14
0 / 100
 200 ms 32120 KB 
#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]);
	}
	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

boat.cpp: In function 'void updatejam(long long int, long long int, long long int)':
boat.cpp:115: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:123: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:164:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i+1<vecx.size();i++){
             ~~~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 32120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 32120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 200 ms 32120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 32120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -