Submission #694641

#	Time	Username	Problem	Language	Result	Execution time	Memory
694641		cig32	Boat (APIO16_boat)	C++17	0 / 100	2088 ms	6228 KiB

boat

#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;
  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
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42