제출 #724386

#제출 시각아이디문제언어결과실행 시간메모리
724386sunwukong123Boat (APIO16_boat)C++14
58 / 100
2048 ms34676 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define FOR(i,s,e) for(int i = s; i <= (int)e; ++i) #define DEC(i,s,e) for(int i = s; i >= (int)e; --i) #define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL #define db(x) cerr << #x << "=" << x << "\n" #define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n" #define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n" #define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n" #define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{" << ite.f << ',' << ite.s << "} "; cerr << "\n" #define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n" #define reach cerr << "LINE: " << __LINE__ << "\n"; #else #define reach #define db(x) #define db2(x,y) #define db3(a,b,c) #define dbv(v) #define dbvp(v) #define dba(a,ss,ee) #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define f first #define s second #define g0(x) get<0>(x) #define g1(x) get<1>(x) #define g2(x) get<2>(x) #define g3(x) get<3>(x) typedef pair <int, int> pi; typedef tuple<int,int,int> ti3; typedef tuple<int,int,int,int> ti4; int rand(int a, int b) { return a + rng() % (b-a+1); } const int MOD = 1e9 + 7; const int inf = (int)1e9 + 500; const long long oo = (long long)1e18 + 500; template <typename T> void chmax(T& a, const T b) { a=max(a,b); } template <typename T> void chmin(T& a, const T b) { a=min(a,b); } const int MAXN = 1005; #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,tune=native") #pragma GCC optimize("O3,unroll-loops") int n; vector<int> points; int L[MAXN],R[MAXN]; int dp[MAXN][MAXN]; // dp(i,c)=number of ways to reach the ith segment with c objects inside the ith segment int S[MAXN]; int sz[MAXN]; int M[MAXN]; int qexp(int a, int b, int mod) { a%=mod; int res = 1; while(b) { if(b&1)res=res*a%mod; a=a*a%mod; b>>=1; } return res; } struct hash_pair { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(pair<uint64_t,uint64_t> x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1); } }; unordered_map<pi,int,hash_pair>memo; int choose(int n, int k) { auto it=memo.find({n,k}); if(it!=memo.end())return it->s; exit(0); int x = 1, y = 1; FOR(i,0,k-1) { y*=n-i; x*=k-i; y%=MOD; x%=MOD; } return memo[{n,k}]=(y*qexp(x,MOD-2,MOD)) % MOD; } int arr[MAXN]; void precomp(int n,int mx) { int x=1,y=1; FOR(i,1,mx) { y*=n-i+1; x*=i; y%=MOD; x%=MOD; memo[{n,i}]=(y*qexp(x,MOD-2,MOD)) % MOD; } } int32_t main() { IAMSPEED cin >> n; FOR(i,1,n){ cin >> L[i] >> R[i]; points.pb(L[i]); points.pb(R[i]+1); } points.pb(-inf); sort(all(points)); points.resize(unique(all(points))-points.begin()); // my ith segment is points[i] to points[i+1] int m=points.size(); FOR(i,0,m-2)sz[i]=points[i+1]-points[i]; FOR(i,1,m-2) { precomp(sz[i],min(sz[i],n)); } FOR(i,0,m-1)S[i]=1; FOR(i,1,n) { int ls=lower_bound(all(points),L[i])-points.begin(); int rs=lower_bound(all(points),R[i]+1)-points.begin(); DEC(j,rs-1,ls){ DEC(k,min({M[j]+1,i,sz[j]}),1){ if(k>1)dp[j][k]=(dp[j][k]+dp[j][k-1])%MOD; else if(j)dp[j][k]=(dp[j][k]+S[j-1])%MOD; if(dp[j][k])chmax(M[j],k); } } memset(S,0,sizeof S); DEC(j,rs-1,ls){ int val = 0; if(j==0){ val=1; } FOR(k,1,min({M[j],i,sz[j]})){ val=(val+dp[j][k]*choose(sz[j],k)%MOD)%MOD; } arr[j]=val; } FOR(j,0,m-1){ if(j)S[j]=(S[j-1]+arr[j])%MOD; else S[j]=1; } } cout<<(S[m-1]-1+MOD)%MOD; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...