oj.uz

Submission #694656

# Submission time Handle Problem Language Result Execution time Memory
694656 2023-02-04T07:52:15 Z cig32 Boat (APIO16_boat) C++17
27 / 100
 2000 ms 6228 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;
      for(int x=0; x<=j; x++) pre[i][j] = (pre[i][j] + nCr(j, x) * nCr(L, x+2)) % 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--) { // O(n^3)
          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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 6228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 6228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 812 KB Output is correct
2 Correct 227 ms 724 KB Output is correct
3 Correct 230 ms 808 KB Output is correct
4 Correct 228 ms 812 KB Output is correct
5 Correct 229 ms 720 KB Output is correct
6 Correct 239 ms 816 KB Output is correct
7 Correct 230 ms 812 KB Output is correct
8 Correct 236 ms 816 KB Output is correct
9 Correct 235 ms 816 KB Output is correct
10 Correct 231 ms 832 KB Output is correct
11 Correct 230 ms 812 KB Output is correct
12 Correct 231 ms 820 KB Output is correct
13 Correct 239 ms 844 KB Output is correct
14 Correct 229 ms 820 KB Output is correct
15 Correct 232 ms 808 KB Output is correct
16 Correct 112 ms 588 KB Output is correct
17 Correct 107 ms 596 KB Output is correct
18 Correct 108 ms 596 KB Output is correct
19 Correct 114 ms 596 KB Output is correct
20 Correct 109 ms 596 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 6228 KB Time limit exceeded
2 Halted 0 ms 0 KB -