Submission #40683

#TimeUsernameProblemLanguageResultExecution timeMemory
40683bogdan10bosBoat (APIO16_boat)C++14
100 / 100
1950 ms18356 KiB
#include <bits/stdc++.h> using namespace std; //#define FILE_IO const int mod = 1e9 + 7; int N, K; int a[1005], b[1005], st[1005], dr[1005]; int dp[1005][4005], sum[1005][4005]; /// primele i, ultimul este in intervalul j int fct[100005], ifct[100005], inv[100005]; int cmb[100005]; int cc[4005][1005]; int cntall[4005]; class Normalize { public: map<int, int> mp; vector<int> ord; void add(int x) { if(mp.count(x)) return; ord.push_back(x); mp[x]; } void normalize() { sort(ord.begin(), ord.end()); for(int i = 0; i < ord.size(); i++) mp[ ord[i] ] = i; } int get(int x) { return mp[x]; } }nrm; int power(int x, int y) { if(y <= 0) return 1; int ans = power( (1LL * x * x) % mod, y >> 1 ); if(y & 1) ans = (1LL * x * ans) % mod; return ans; } void pre(int K) { fct[0] = 1; for(int i = 1; i <= K; i++) fct[i] = (1LL * fct[i - 1] * i) % mod; ifct[K] = power(fct[K], mod - 2); for(int i = K - 1; i >= 0; i--) ifct[i] = (1LL * ifct[i + 1] * (i + 1)) % mod; for(int i = 1; i <= K; i++) inv[i] = power(i, mod - 2); } int C(int N, int K) { if(K > N) return 0; int ans = (1LL * fct[N] * ifct[K]) % mod; ans = (1LL * ans * ifct[N - K]) % mod; return ans; } int main() { #ifdef FILE_IO freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); #endif pre(1e4); scanf("%d", &N); for(int i = 1; i <= N; i++) { scanf("%d%d", &a[i], &b[i]); nrm.add(a[i]); nrm.add(b[i]); } nrm.normalize(); for(int i = 1; i <= N; i++) { st[i] = nrm.get(a[i]); dr[i] = nrm.get(b[i]); for(int j = 2 * st[i] + 2; j < 2 * dr[i] + 2; j += 2) cntall[j]++; } K = nrm.ord.size(); for(int i = 2; i <= 2 * K - 1; i += 2) { int lft = nrm.ord[i / 2 - 1]; int rgt = nrm.ord[i / 2]; int sz = rgt - lft - 1; cmb[0] = 1; for(int k = 1; k <= cntall[i]; k++) { cmb[k] = (1LL * cmb[k - 1] * (sz - k + 1)) % mod; cmb[k] = (1LL * cmb[k] * inv[k]) % mod; } for(int j = 1; j <= cntall[i]; j++) for(int k = 0; k < j; k++) cc[i][j] = (cc[i][j] + (1LL * cmb[k + 1] * C(j - 1, k)) % mod) % mod; } for(int i = 0; i <= 2 * K - 1; i++) dp[0][i] = sum[0][i] = 1; int ans = 0; for(int i = 1; i <= N; i++) { sum[i][0] = sum[i - 1][0]; for(int j = 1; j <= 2 * K - 1; j++) { dp[i][j] = dp[i][j - 1]; if(j & 1) { int x = nrm.ord[j / 2]; if(a[i] <= x && x <= b[i]) dp[i][j] = (dp[i][j] + sum[i - 1][j - 1]) % mod; } else { int lft = nrm.ord[j / 2 - 1]; int rgt = nrm.ord[j / 2]; int sz = rgt - lft - 1; if(a[i] <= lft && rgt <= b[i]) { cmb[0] = 1; for(int k = 1; k <= i; k++) { cmb[k] = (1LL * cmb[k - 1] * (sz - k + 1)) % mod; cmb[k] = (1LL * cmb[k] * inv[k]) % mod; } int cnt = 0; for(int k = i; k > 0; k--) { if(a[k] <= lft && rgt <= b[k]) cnt++; int ans = cc[j][cnt]; dp[i][j] += (1LL * dp[k - 1][j - 1] * ans) % mod; dp[i][j] %= mod; } } } sum[i][j] = (sum[i - 1][j] + dp[i][j]) % mod; } ans = (ans + dp[i][2 * K - 1]) % mod; } printf("%d\n", ans); return 0; }

Compilation message (stderr)

boat.cpp: In member function 'void Normalize::normalize()':
boat.cpp:33:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < ord.size(); i++)
                          ^
boat.cpp: In function 'int main()':
boat.cpp:75:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
boat.cpp:78:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i], &b[i]);
                                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...