oj.uz

Submission #694663

# Submission time Handle Problem Language Result Execution time Memory
694663 2023-02-04T07:56:48 Z cig32 Boat (APIO16_boat) C++17
36 / 100
 2000 ms 12116 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];
  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] + nCr(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 313 ms 6300 KB Output is correct
2 Correct 309 ms 6304 KB Output is correct
3 Correct 307 ms 6304 KB Output is correct
4 Correct 300 ms 6300 KB Output is correct
5 Correct 301 ms 6304 KB Output is correct
6 Correct 303 ms 6300 KB Output is correct
7 Correct 293 ms 6296 KB Output is correct
8 Correct 306 ms 6316 KB Output is correct
9 Correct 309 ms 6304 KB Output is correct
10 Correct 306 ms 6296 KB Output is correct
11 Correct 305 ms 6304 KB Output is correct
12 Correct 316 ms 6308 KB Output is correct
13 Correct 305 ms 6300 KB Output is correct
14 Correct 321 ms 6308 KB Output is correct
15 Correct 310 ms 6308 KB Output is correct
16 Correct 65 ms 1376 KB Output is correct
17 Correct 67 ms 1456 KB Output is correct
18 Correct 64 ms 1424 KB Output is correct
19 Correct 63 ms 1460 KB Output is correct
20 Correct 63 ms 1432 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 6300 KB Output is correct
2 Correct 309 ms 6304 KB Output is correct
3 Correct 307 ms 6304 KB Output is correct
4 Correct 300 ms 6300 KB Output is correct
5 Correct 301 ms 6304 KB Output is correct
6 Correct 303 ms 6300 KB Output is correct
7 Correct 293 ms 6296 KB Output is correct
8 Correct 306 ms 6316 KB Output is correct
9 Correct 309 ms 6304 KB Output is correct
10 Correct 306 ms 6296 KB Output is correct
11 Correct 305 ms 6304 KB Output is correct
12 Correct 316 ms 6308 KB Output is correct
13 Correct 305 ms 6300 KB Output is correct
14 Correct 321 ms 6308 KB Output is correct
15 Correct 310 ms 6308 KB Output is correct
16 Correct 65 ms 1376 KB Output is correct
17 Correct 67 ms 1456 KB Output is correct
18 Correct 64 ms 1424 KB Output is correct
19 Correct 63 ms 1460 KB Output is correct
20 Correct 63 ms 1432 KB Output is correct
21 Correct 1308 ms 11168 KB Output is correct
22 Correct 1266 ms 11324 KB Output is correct
23 Correct 1134 ms 11124 KB Output is correct
24 Correct 1170 ms 11032 KB Output is correct
25 Correct 1143 ms 11216 KB Output is correct
26 Correct 1379 ms 10700 KB Output is correct
27 Correct 1431 ms 10964 KB Output is correct
28 Correct 1380 ms 10828 KB Output is correct
29 Correct 1375 ms 10736 KB Output is correct
30 Execution timed out 2079 ms 12116 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 808 KB Output is correct
2 Correct 82 ms 940 KB Output is correct
3 Correct 78 ms 812 KB Output is correct
4 Correct 80 ms 804 KB Output is correct
5 Correct 79 ms 724 KB Output is correct
6 Correct 81 ms 812 KB Output is correct
7 Correct 86 ms 804 KB Output is correct
8 Correct 96 ms 724 KB Output is correct
9 Correct 93 ms 808 KB Output is correct
10 Correct 84 ms 724 KB Output is correct
11 Correct 81 ms 804 KB Output is correct
12 Correct 79 ms 808 KB Output is correct
13 Correct 79 ms 804 KB Output is correct
14 Correct 79 ms 804 KB Output is correct
15 Correct 84 ms 804 KB Output is correct
16 Correct 36 ms 596 KB Output is correct
17 Correct 36 ms 596 KB Output is correct
18 Correct 36 ms 596 KB Output is correct
19 Correct 37 ms 592 KB Output is correct
20 Correct 38 ms 576 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 6300 KB Output is correct
2 Correct 309 ms 6304 KB Output is correct
3 Correct 307 ms 6304 KB Output is correct
4 Correct 300 ms 6300 KB Output is correct
5 Correct 301 ms 6304 KB Output is correct
6 Correct 303 ms 6300 KB Output is correct
7 Correct 293 ms 6296 KB Output is correct
8 Correct 306 ms 6316 KB Output is correct
9 Correct 309 ms 6304 KB Output is correct
10 Correct 306 ms 6296 KB Output is correct
11 Correct 305 ms 6304 KB Output is correct
12 Correct 316 ms 6308 KB Output is correct
13 Correct 305 ms 6300 KB Output is correct
14 Correct 321 ms 6308 KB Output is correct
15 Correct 310 ms 6308 KB Output is correct
16 Correct 65 ms 1376 KB Output is correct
17 Correct 67 ms 1456 KB Output is correct
18 Correct 64 ms 1424 KB Output is correct
19 Correct 63 ms 1460 KB Output is correct
20 Correct 63 ms 1432 KB Output is correct
21 Correct 1308 ms 11168 KB Output is correct
22 Correct 1266 ms 11324 KB Output is correct
23 Correct 1134 ms 11124 KB Output is correct
24 Correct 1170 ms 11032 KB Output is correct
25 Correct 1143 ms 11216 KB Output is correct
26 Correct 1379 ms 10700 KB Output is correct
27 Correct 1431 ms 10964 KB Output is correct
28 Correct 1380 ms 10828 KB Output is correct
29 Correct 1375 ms 10736 KB Output is correct
30 Execution timed out 2079 ms 12116 KB Time limit exceeded
31 Halted 0 ms 0 KB -