oj.uz

Submission #694630

# Submission time Handle Problem Language Result Execution time Memory
694630 2023-02-04T07:28:57 Z cig32 Boat (APIO16_boat) C++17
9 / 100
 2000 ms 7608 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 nCr(int n, int r) {
  if(n < r) return 0;
  int ans = 1;
  if(r > n-r) r = n-r;
  for(int i=1; i<=r; i++) ans = (ans * inv(i)) % MOD;
  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], invnums[n+1];
  fac[0] = 1;
  for(int i=1; i<=n; i++) {
    fac[i] = (fac[i-1] * i) % MOD;
    invnums[i] = inv(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;
  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];
          dp[i][j] %= MOD;
        }
        // Consider taking same ranges
        int totn = 0;
        int L = ranges[j].second-ranges[j].first+1;

        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) {
            int sum = 0;
            // Take the same range, with the leftmost same range at k
            // Calc now
            for(int x=0; x<=totn; x++) {
              sum += nCr(totn, x) * nCr(L, x+2);
              sum %= MOD;
            }
            dp[i][j] += sum * (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";
}

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
*/

Compilation message

boat.cpp: In function 'void solve(long long int)':
boat.cpp:35:17: warning: variable 'invnums' set but not used [-Wunused-but-set-variable]
   35 |   int fac[n+1], invnums[n+1];
      |                 ^~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4340 KB Output is correct
2 Correct 8 ms 4308 KB Output is correct
3 Correct 10 ms 4308 KB Output is correct
4 Correct 8 ms 4296 KB Output is correct
5 Correct 8 ms 4308 KB Output is correct
6 Correct 7 ms 4308 KB Output is correct
7 Correct 7 ms 4376 KB Output is correct
8 Correct 7 ms 4300 KB Output is correct
9 Correct 7 ms 4308 KB Output is correct
10 Correct 7 ms 4308 KB Output is correct
11 Correct 7 ms 4308 KB Output is correct
12 Correct 7 ms 4372 KB Output is correct
13 Correct 6 ms 4300 KB Output is correct
14 Correct 7 ms 4308 KB Output is correct
15 Correct 7 ms 4372 KB Output is correct
16 Correct 5 ms 980 KB Output is correct
17 Correct 6 ms 1108 KB Output is correct
18 Correct 5 ms 980 KB Output is correct
19 Correct 5 ms 1104 KB Output is correct
20 Correct 5 ms 980 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4340 KB Output is correct
2 Correct 8 ms 4308 KB Output is correct
3 Correct 10 ms 4308 KB Output is correct
4 Correct 8 ms 4296 KB Output is correct
5 Correct 8 ms 4308 KB Output is correct
6 Correct 7 ms 4308 KB Output is correct
7 Correct 7 ms 4376 KB Output is correct
8 Correct 7 ms 4300 KB Output is correct
9 Correct 7 ms 4308 KB Output is correct
10 Correct 7 ms 4308 KB Output is correct
11 Correct 7 ms 4308 KB Output is correct
12 Correct 7 ms 4372 KB Output is correct
13 Correct 6 ms 4300 KB Output is correct
14 Correct 7 ms 4308 KB Output is correct
15 Correct 7 ms 4372 KB Output is correct
16 Correct 5 ms 980 KB Output is correct
17 Correct 6 ms 1108 KB Output is correct
18 Correct 5 ms 980 KB Output is correct
19 Correct 5 ms 1104 KB Output is correct
20 Correct 5 ms 980 KB Output is correct
21 Execution timed out 2078 ms 7608 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4340 KB Output is correct
2 Correct 8 ms 4308 KB Output is correct
3 Correct 10 ms 4308 KB Output is correct
4 Correct 8 ms 4296 KB Output is correct
5 Correct 8 ms 4308 KB Output is correct
6 Correct 7 ms 4308 KB Output is correct
7 Correct 7 ms 4376 KB Output is correct
8 Correct 7 ms 4300 KB Output is correct
9 Correct 7 ms 4308 KB Output is correct
10 Correct 7 ms 4308 KB Output is correct
11 Correct 7 ms 4308 KB Output is correct
12 Correct 7 ms 4372 KB Output is correct
13 Correct 6 ms 4300 KB Output is correct
14 Correct 7 ms 4308 KB Output is correct
15 Correct 7 ms 4372 KB Output is correct
16 Correct 5 ms 980 KB Output is correct
17 Correct 6 ms 1108 KB Output is correct
18 Correct 5 ms 980 KB Output is correct
19 Correct 5 ms 1104 KB Output is correct
20 Correct 5 ms 980 KB Output is correct
21 Execution timed out 2078 ms 7608 KB Time limit exceeded
22 Halted 0 ms 0 KB -