| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 88943 |
2018-12-10T06:09:38 Z |
ckodser |
Boat (APIO16_boat) |
C++14 |
|
200 ms |
32224 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=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
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++){
~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
177 ms |
16120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
177 ms |
16120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
200 ms |
32224 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 |
Incorrect |
177 ms |
16120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
