oj.uz

Submission #694670

# Submission time Handle Problem Language Result Execution time Memory
694670 2023-02-04T07:57:58 Z cig32 Boat (APIO16_boat) C++17
100 / 100
 1854 ms 14328 KB 
#include "bits/stdc++.h"
#define int long long
#define double long double
using namespace std;
mt19937_64 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  return uniform_int_distribution<int>(x, y)(rng);
}
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;

int bm(int b, int p) {
  if(p==0) return 1;
  int r = bm(b, p/2);
  if(p & 1) return (((r*r) % MOD) * b )% MOD;
  return (r*r) % MOD;
}

int inv(int b) {
  return bm(b, MOD - 2);
}

int invfac[505];

int nCr(int n, int r) {
  if(n < r) return 0;
  if(r > n-r) r = n-r;
  if(r == 0) return 1;
  int ans = invfac[r];
  for(int i=n-r+1; i<=n; i++) ans = (ans * i) % MOD;
  return ans;
}

void solve(int tc) {
  int n;
  cin >> n;
  int fac[n+1];
  fac[0] = 1;
  for(int i=1; i<=n; i++) {
    fac[i] = (fac[i-1] * i) % MOD;
    invfac[i] = inv(fac[i]);
  }
  pair<int, int> p[n+1];
  for(int i=1; i<=n; i++) cin >> p[i].first >> p[i].second;
  set<int> starts, ends;
  for(int i=1; i<=n; i++) {
    starts.insert(p[i].first);
    ends.insert(p[i].second);
  }
  starts.insert(MOD);
  ends.insert(MOD);
  set<pair<int, int> > temp;
  for(int i=1; i<=n; i++) {
    int now = p[i].first;
    while(1) {
      int one = *starts.lower_bound(now+1);
      int two = *ends.lower_bound(now);
      int res = min(one - 1, two);
      res = min(res, p[i].second);
      temp.insert({now, res});
      if(res == p[i].second) break;
      now = res+1;
    }
  }
  vector<pair<int, int> > ranges;
  ranges.push_back({-1, -1});
  for(pair<int, int> x: temp) ranges.push_back(x);
  int m = ranges.size()-1; // O(n)
  int dp[n+1][m+1]; // O(n^2)
  int sum[n+1][m+1]; // sum[i][j] = sum(dp[i][0], dp[i][1], ..., dp[i][j])
  /*
  dp[i][j] = Number of ways, using the first i students only,
  and guarantee using the i-th. With the i-th using the j-th range.
  */
  for(int i=0; i<=n; i++) {
    for(int j=0; j<=m; j++) {
      dp[i][j] = sum[i][j] = 0;
    }
  }
  dp[0][0] = 1;
  for(int i=0; i<=m; i++) sum[0][i] = 1;
  int pre[m+1][n+1];

  int table[n+1][n+1];
  for(int i=0; i<=n; i++) for(int j=0; j<=i; j++) table[i][j] = nCr(i, j);
  for(int i=1; i<=m; i++) {
    int L = ranges[i].second - ranges[i].first + 1;
    for(int j=0; j<=n; j++) {
      pre[i][j] = 0;
      int wow = L;
      for(int x=0; x<=j; x++) {
        wow = (wow * (L-x-1)) % MOD;
        if(L >= x+2) {
          int bruh = (wow * invfac[x+2]) % MOD;
          pre[i][j] = (pre[i][j] + table[j][x] * bruh) % MOD;
        }
      }
    }
  }
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) { // O(n)
      if(p[i].first <= ranges[j].first && ranges[j].second <= p[i].second) {
        // Consider taking different ranges
        for(int k=0; k<i; k++) {
          dp[i][j] += sum[k][j-1] * (ranges[j].second - ranges[j].first + 1);
          dp[i][j] %= MOD;
        }
        // Consider taking same ranges
        int totn = 0;
        int ps[i+1];
        ps[0] = sum[0][j-1];
        for(int k=1; k<=i; k++) ps[k] = (ps[k-1] + sum[k][j-1]) % MOD;
        for(int k=i-1; k>=0; k--) { 
          if(p[k].first <= ranges[j].first && ranges[j].second <= p[k].second) {
            dp[i][j] += pre[j][totn] * (k==0 ? 0 : ps[k-1]);
            dp[i][j] %= MOD;
          }
          if(k > 0) totn += (p[k].first <= ranges[j].first && ranges[j].second <= p[k].second);
        }
      }
      sum[i][j] = sum[i][j-1] + dp[i][j];
      sum[i][j] %= MOD;
    }
  }
  int answer = 0;
  for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) answer = (answer + dp[i][j]) % MOD;
  cout << answer << "\n";
  /*
  for(int i=1; i<=m; i++) cout << ranges[i].first << " " << ranges[i].second << "\n";
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
      cout << dp[i][j] << " \n"[j == m];
    }
  }
  */
}

int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t=1; //cin>>t;
  for(int i=1; i<=t; i++) solve(i);
}
/*
If there are totn instances of range j in between k<x<i 
Then let the range size = L
Possibilities:

Take 0 from totn: nCr(totn, 0) * nCr(L, 1)
Take x from totn: nCr(totn, x) * nCr(L, x+1)

Answer is sum of nCr(totn, x) * nCr(L, x+1) from 0 <= x <= totn
L can be very large
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 8276 KB Output is correct
2 Correct 337 ms 8276 KB Output is correct
3 Correct 339 ms 8276 KB Output is correct
4 Correct 340 ms 8396 KB Output is correct
5 Correct 334 ms 8276 KB Output is correct
6 Correct 335 ms 8284 KB Output is correct
7 Correct 342 ms 8276 KB Output is correct
8 Correct 335 ms 8276 KB Output is correct
9 Correct 337 ms 8276 KB Output is correct
10 Correct 336 ms 8276 KB Output is correct
11 Correct 344 ms 8280 KB Output is correct
12 Correct 339 ms 8276 KB Output is correct
13 Correct 340 ms 8276 KB Output is correct
14 Correct 358 ms 8276 KB Output is correct
15 Correct 336 ms 8276 KB Output is correct
16 Correct 100 ms 3284 KB Output is correct
17 Correct 103 ms 3432 KB Output is correct
18 Correct 102 ms 3416 KB Output is correct
19 Correct 104 ms 3412 KB Output is correct
20 Correct 102 ms 3412 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 8276 KB Output is correct
2 Correct 337 ms 8276 KB Output is correct
3 Correct 339 ms 8276 KB Output is correct
4 Correct 340 ms 8396 KB Output is correct
5 Correct 334 ms 8276 KB Output is correct
6 Correct 335 ms 8284 KB Output is correct
7 Correct 342 ms 8276 KB Output is correct
8 Correct 335 ms 8276 KB Output is correct
9 Correct 337 ms 8276 KB Output is correct
10 Correct 336 ms 8276 KB Output is correct
11 Correct 344 ms 8280 KB Output is correct
12 Correct 339 ms 8276 KB Output is correct
13 Correct 340 ms 8276 KB Output is correct
14 Correct 358 ms 8276 KB Output is correct
15 Correct 336 ms 8276 KB Output is correct
16 Correct 100 ms 3284 KB Output is correct
17 Correct 103 ms 3432 KB Output is correct
18 Correct 102 ms 3416 KB Output is correct
19 Correct 104 ms 3412 KB Output is correct
20 Correct 102 ms 3412 KB Output is correct
21 Correct 1137 ms 13100 KB Output is correct
22 Correct 1128 ms 13272 KB Output is correct
23 Correct 1087 ms 13076 KB Output is correct
24 Correct 1098 ms 12988 KB Output is correct
25 Correct 1113 ms 13040 KB Output is correct
26 Correct 1462 ms 12760 KB Output is correct
27 Correct 1458 ms 13040 KB Output is correct
28 Correct 1440 ms 12728 KB Output is correct
29 Correct 1444 ms 12696 KB Output is correct
30 Correct 752 ms 14128 KB Output is correct
31 Correct 767 ms 14296 KB Output is correct
32 Correct 782 ms 14036 KB Output is correct
33 Correct 813 ms 14156 KB Output is correct
34 Correct 802 ms 14128 KB Output is correct
35 Correct 788 ms 14164 KB Output is correct
36 Correct 808 ms 14168 KB Output is correct
37 Correct 789 ms 14164 KB Output is correct
38 Correct 792 ms 14128 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 852 KB Output is correct
2 Correct 12 ms 904 KB Output is correct
3 Correct 12 ms 852 KB Output is correct
4 Correct 13 ms 908 KB Output is correct
5 Correct 13 ms 908 KB Output is correct
6 Correct 17 ms 852 KB Output is correct
7 Correct 16 ms 912 KB Output is correct
8 Correct 15 ms 852 KB Output is correct
9 Correct 16 ms 908 KB Output is correct
10 Correct 15 ms 852 KB Output is correct
11 Correct 12 ms 908 KB Output is correct
12 Correct 12 ms 908 KB Output is correct
13 Correct 12 ms 904 KB Output is correct
14 Correct 14 ms 852 KB Output is correct
15 Correct 12 ms 852 KB Output is correct
16 Correct 7 ms 688 KB Output is correct
17 Correct 7 ms 596 KB Output is correct
18 Correct 7 ms 596 KB Output is correct
19 Correct 7 ms 692 KB Output is correct
20 Correct 8 ms 680 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 8276 KB Output is correct
2 Correct 337 ms 8276 KB Output is correct
3 Correct 339 ms 8276 KB Output is correct
4 Correct 340 ms 8396 KB Output is correct
5 Correct 334 ms 8276 KB Output is correct
6 Correct 335 ms 8284 KB Output is correct
7 Correct 342 ms 8276 KB Output is correct
8 Correct 335 ms 8276 KB Output is correct
9 Correct 337 ms 8276 KB Output is correct
10 Correct 336 ms 8276 KB Output is correct
11 Correct 344 ms 8280 KB Output is correct
12 Correct 339 ms 8276 KB Output is correct
13 Correct 340 ms 8276 KB Output is correct
14 Correct 358 ms 8276 KB Output is correct
15 Correct 336 ms 8276 KB Output is correct
16 Correct 100 ms 3284 KB Output is correct
17 Correct 103 ms 3432 KB Output is correct
18 Correct 102 ms 3416 KB Output is correct
19 Correct 104 ms 3412 KB Output is correct
20 Correct 102 ms 3412 KB Output is correct
21 Correct 1137 ms 13100 KB Output is correct
22 Correct 1128 ms 13272 KB Output is correct
23 Correct 1087 ms 13076 KB Output is correct
24 Correct 1098 ms 12988 KB Output is correct
25 Correct 1113 ms 13040 KB Output is correct
26 Correct 1462 ms 12760 KB Output is correct
27 Correct 1458 ms 13040 KB Output is correct
28 Correct 1440 ms 12728 KB Output is correct
29 Correct 1444 ms 12696 KB Output is correct
30 Correct 752 ms 14128 KB Output is correct
31 Correct 767 ms 14296 KB Output is correct
32 Correct 782 ms 14036 KB Output is correct
33 Correct 813 ms 14156 KB Output is correct
34 Correct 802 ms 14128 KB Output is correct
35 Correct 788 ms 14164 KB Output is correct
36 Correct 808 ms 14168 KB Output is correct
37 Correct 789 ms 14164 KB Output is correct
38 Correct 792 ms 14128 KB Output is correct
39 Correct 13 ms 852 KB Output is correct
40 Correct 12 ms 904 KB Output is correct
41 Correct 12 ms 852 KB Output is correct
42 Correct 13 ms 908 KB Output is correct
43 Correct 13 ms 908 KB Output is correct
44 Correct 17 ms 852 KB Output is correct
45 Correct 16 ms 912 KB Output is correct
46 Correct 15 ms 852 KB Output is correct
47 Correct 16 ms 908 KB Output is correct
48 Correct 15 ms 852 KB Output is correct
49 Correct 12 ms 908 KB Output is correct
50 Correct 12 ms 908 KB Output is correct
51 Correct 12 ms 904 KB Output is correct
52 Correct 14 ms 852 KB Output is correct
53 Correct 12 ms 852 KB Output is correct
54 Correct 7 ms 688 KB Output is correct
55 Correct 7 ms 596 KB Output is correct
56 Correct 7 ms 596 KB Output is correct
57 Correct 7 ms 692 KB Output is correct
58 Correct 8 ms 680 KB Output is correct
59 Correct 1500 ms 14200 KB Output is correct
60 Correct 1463 ms 14204 KB Output is correct
61 Correct 1417 ms 14208 KB Output is correct
62 Correct 1462 ms 14328 KB Output is correct
63 Correct 1445 ms 14200 KB Output is correct
64 Correct 1808 ms 14200 KB Output is correct
65 Correct 1786 ms 14200 KB Output is correct
66 Correct 1816 ms 14156 KB Output is correct
67 Correct 1817 ms 14204 KB Output is correct
68 Correct 1854 ms 14288 KB Output is correct
69 Correct 1338 ms 14204 KB Output is correct
70 Correct 1365 ms 14196 KB Output is correct
71 Correct 1339 ms 14216 KB Output is correct
72 Correct 1326 ms 14212 KB Output is correct
73 Correct 1353 ms 14324 KB Output is correct
74 Correct 299 ms 4440 KB Output is correct
75 Correct 293 ms 4516 KB Output is correct
76 Correct 290 ms 4496 KB Output is correct
77 Correct 303 ms 4480 KB Output is correct
78 Correct 292 ms 4448 KB Output is correct