#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4")
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef unsigned long long int ull;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w)
{
cout<<w.size()<<endl;
for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
if (w.size()) cout<<w[w.size()-1]<<endl;
}
void M998()
{
swap(MOD,MOD2);
}
ll raand()
{
ll a=rund();
a*=RAND_MAX;
a+=rund();
return a;
}
#define rand raand
ll raaand()
{
return raand()*(MOD-7)+raand();
}
string to_upper(string a)
{
for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
return a;
}
string to_lower(string a)
{
for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
return a;
}
ll sti(string a)
{
ll k=0;
for (int i=0;i<(int)a.size();++i)
{
k*=10;
k+=a[i]-'0';
}
return k;
}
string its(ll k)
{
if (k==0) return "0";
string a;
while (k)
{
a.push_back((k%10)+'0');
k/=10;
}
reverse(a.begin(),a.end());
return a;
}
ll min(ll a,int b)
{
if (a<b) return a;
return b;
}
ll min(int a,ll b)
{
if (a<b) return a;
return b;
}
ll max(ll a,int b)
{
if (a>b) return a;
return b;
}
ll max(int a,ll b)
{
if (a>b) return a;
return b;
}
ll gcd(ll a,ll b)
{
if (b==0) return a;
return gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
return a/gcd(a,b)*b;
}
template<class T,class K>
pair<T,K> mp(T a,K b)
{
return make_pair(a,b);
}
inline int mult(ll a,ll b)
{
return (a*b)%MOD;
}
inline int pot(int n,int k)
{
if (k==0) return 1;
ll a=pot(n,k/2);
a=mult(a,a);
if (k%2) return mult(a,n);
else return a;
}
int divide(int a,int b)
{
return mult(a,pot(b,MOD-2));
}
inline int sub(int a,int b)
{
if (a-b>=0) return a-b;
return a-b+MOD;
}
inline int add(int a,int b)
{
if (a+b>=MOD) return a+b-MOD;
return a+b;
}
bool prime(ll a)
{
if (a==1) return 0;
for (int i=2;i<=round(sqrt(a));++i)
{
if (a%i==0) return 0;
}
return 1;
}
ll has(string x)
{
ll h1=0,h2=0;
x=to_lower(x);
for (char a: x)
{
h1*=bases[0];
h1+=a-'a';
h1%=bases[3];
h2*=bases[1];
h2+=a-'a';
h2%=bases[4];
}
return h1*(MOD+13893829)+h2;
}
const int N=1020,M=1<<10,SZ=2907;
int n,fac[N],inf[N],dp[N],pre[N],in[N];
pii h[N];
vector<pii> ha[N][SZ];
vector<pii> so;
vector<int> poi;
set<int> poo;
int seg[M+N][N];
int po[N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void addH(int i,int j,int x)
{
int i1=i;
i=(i^0x183b4278)%SZ;
for (auto &a: ha[j][i]) if (a.y==i1)
{
a.x=add(a.x,x);
return;
}
ha[j][i].pb({x,i1});
}
void upd(int i,int j,int x)
{
i+=M;
seg[i][j]=add(seg[i][j],x);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
for (int i=0;i<10;++i) bases.push_back((rand()%MOD+13893829)%MOD);
cin>>n;
fac[0]=1;
const int MAX=1001;
for (int i=1;i<=MAX;++i) fac[i]=mult(fac[i-1],i),in[i]=divide(1,i);
inf[MAX]=divide(1,fac[MAX]);
for (int i=MAX-1;i>=0;--i) inf[i]=mult(inf[i+1],i+1);
for (int i=0;i<n;++i) cin>>h[i].x>>h[i].y,poo.insert(h[i].x),poo.insert(h[i].y+1);
for (auto a: poo) poi.pb(a);
for (int i=1;i<poi.size();++i) so.pb({poi[i-1],poi[i]});
so.pb({poi.back(),MOD-6});
upd(0,0,1);
for (int k=0;k<=MAX;++k) pre[k]+=1;
dp[0]=1;
for (int i=0;i<n;++i)
{
for (int j=upper_bound(so.begin(),so.end(),mp(h[i].y+1,0))-so.begin()-1;j>=0 && so[j].x>=h[i].x;--j)
{
int jj=j+1;
for (int k=MAX/2-1;k>=0;--k) upd(jj,k+1,seg[jj+M][k]);
//for (int k=MAX-1;k>=0;--k) upd(jj,k,-seg[jj+M][k+1]);
for (int k=0;k<1;++k) upd(jj,k,pre[j]);
//cout<<en<<i<<' '<<jj<<' '<<so[j].x<<' '<<so[j].y;
int re=0,r1=1;
for (int k=0;k<min(MAX,so[j].y-so[j].x);++k)
{
r1=mult(r1,so[j].y-so[j].x-k);
r1=mult(r1,in[k+1]);
re=add(re,mult(r1,seg[jj+M][k]));
}
for (int k=jj;k<=MAX;++k) pre[k]=add(pre[k],sub(re,dp[jj]));
dp[jj]=re;
//cout<<' '<<re<<endl;
//cout<<i<<' '<<j<<' '<<so[j].x<<' '<<so[j].y<<endl;
//for (int k=0;k<MAX;++k) cout<<seg[jj+M][k]<<' ';
//cout<<endl<<en<<endl;
//upd(j+1,mult(get(0,j+1),so[j].y-so[j].x));
}
}
int res=0;
for (int i=1;i<=so.size();++i) for (int k=0;k<min(MAX,so[i-1].y-so[i-1].x);++k) if (1)
{
int r1=1;
for (int j=so[i-1].y-so[i-1].x;j>=so[i-1].y-so[i-1].x-k;--j) r1=mult(r1,j);
r1=mult(r1,inf[k+1]);
r1=mult(r1,seg[i+M][k]);
//if (r1) cout<<i<<' '<<k<<' '<<r1<<endl;
res=add(res,r1);
}
cout<<res;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:231:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1;i<poi.size();++i) so.pb({poi[i-1],poi[i]});
~^~~~~~~~~~~
boat.cpp:262:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1;i<=so.size();++i) for (int k=0;k<min(MAX,so[i-1].y-so[i-1].x);++k) if (1)
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2060 ms |
73080 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2060 ms |
73080 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
70904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2060 ms |
73080 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
