oj.uz

Submission #833040

# Submission time Handle Problem Language Result Execution time Memory
833040 2023-08-21T20:33:46 Z erray Boat (APIO16_boat) C++17
9 / 100
 741 ms 4428 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/eagle/ioi22/d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

constexpr int md = int(1e9) + 7;
int add(int x, int y) {
  if ((x += y) > md) {
    x -= md;
  }
  return x;
}
int mul(int x, int y) {
  return 1LL * x * y % md;
}
int power(int x, int p) {
  int res = 1;
  while (p > 0) {
    if (p & 1) {
      res = mul(res, x);
    }
    x = mul(x, x);
    p >>= 1;
  }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i] >> B[i];
    ++B[i];
  }
  vector<int> inv(N + 1);
  for (int i = 1; i <= N; ++i) {
    inv[i] = power(i, md - 2);
  }
  debug(inv);
  vector<int> ranges(2 * N);
  for (int i = 0; i < N; ++i) {
    ranges[2 * i] = A[i];
    ranges[2 * i + 1] = B[i];
  }
  sort(ranges.begin(), ranges.end());
  ranges.erase(unique(ranges.begin(), ranges.end()), ranges.end());
  const int S = int(ranges.size());
  debug(ranges);
  vector<vector<int>> binom(S - 1, vector<int>(N + 1));
  for (int i = 0; i < S - 1; ++i) {
    int diff = ranges[i + 1] - ranges[i];
    binom[i][0] = 1;
    for (int j = 1; j <= min(N, diff); ++j) {
      binom[i][j] = mul(mul(binom[i][j - 1],  (diff - j + 1)), inv[j]);
    }
  }
  debug(binom);
  vector<vector<int>> dp(S, vector<int>(N + 1));
  for (int i = 0; i < S; ++i) {
    dp[i][0] = 1;
  }
  for (int i = 0; i < N; ++i) {
    int nw = 1;
    for (int j = 0; j < S - 1; ++j) {
      int a = 0;
      bool in_range = (A[i] <= ranges[j] && ranges[j + 1] <= B[i]);
      debug(j, nw);
      for (int k = N - 1; k >= 0; --k) {
        if (k != 0) {
          a = add(a, mul(dp[j][k], binom[j][k]));
        } 
        if (in_range) {
          dp[j][k + 1] = add(dp[j][k + 1], mul(dp[j][k], nw));
        }
      }
      nw = add(nw, a);
    }
    debug(i, dp);
  }
  int ans = 0;
  for (int i = 0; i < S - 1; ++i) {
    for (int j = 1; j <= N; ++j) {
      ans = add(ans, mul(dp[i][j], binom[i][j]));
    }
  }
  cout << ans << '\n';
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 4312 KB Output is correct
2 Correct 613 ms 4428 KB Output is correct
3 Correct 627 ms 4308 KB Output is correct
4 Correct 629 ms 4316 KB Output is correct
5 Correct 612 ms 4316 KB Output is correct
6 Correct 621 ms 4320 KB Output is correct
7 Correct 623 ms 4320 KB Output is correct
8 Correct 622 ms 4316 KB Output is correct
9 Correct 635 ms 4320 KB Output is correct
10 Correct 628 ms 4316 KB Output is correct
11 Correct 637 ms 4320 KB Output is correct
12 Correct 626 ms 4316 KB Output is correct
13 Correct 630 ms 4316 KB Output is correct
14 Correct 624 ms 4316 KB Output is correct
15 Correct 632 ms 4320 KB Output is correct
16 Correct 107 ms 980 KB Output is correct
17 Correct 115 ms 980 KB Output is correct
18 Correct 110 ms 980 KB Output is correct
19 Correct 117 ms 980 KB Output is correct
20 Correct 111 ms 1052 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 4312 KB Output is correct
2 Correct 613 ms 4428 KB Output is correct
3 Correct 627 ms 4308 KB Output is correct
4 Correct 629 ms 4316 KB Output is correct
5 Correct 612 ms 4316 KB Output is correct
6 Correct 621 ms 4320 KB Output is correct
7 Correct 623 ms 4320 KB Output is correct
8 Correct 622 ms 4316 KB Output is correct
9 Correct 635 ms 4320 KB Output is correct
10 Correct 628 ms 4316 KB Output is correct
11 Correct 637 ms 4320 KB Output is correct
12 Correct 626 ms 4316 KB Output is correct
13 Correct 630 ms 4316 KB Output is correct
14 Correct 624 ms 4316 KB Output is correct
15 Correct 632 ms 4320 KB Output is correct
16 Correct 107 ms 980 KB Output is correct
17 Correct 115 ms 980 KB Output is correct
18 Correct 110 ms 980 KB Output is correct
19 Correct 117 ms 980 KB Output is correct
20 Correct 111 ms 1052 KB Output is correct
21 Incorrect 741 ms 3956 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 4312 KB Output is correct
2 Correct 613 ms 4428 KB Output is correct
3 Correct 627 ms 4308 KB Output is correct
4 Correct 629 ms 4316 KB Output is correct
5 Correct 612 ms 4316 KB Output is correct
6 Correct 621 ms 4320 KB Output is correct
7 Correct 623 ms 4320 KB Output is correct
8 Correct 622 ms 4316 KB Output is correct
9 Correct 635 ms 4320 KB Output is correct
10 Correct 628 ms 4316 KB Output is correct
11 Correct 637 ms 4320 KB Output is correct
12 Correct 626 ms 4316 KB Output is correct
13 Correct 630 ms 4316 KB Output is correct
14 Correct 624 ms 4316 KB Output is correct
15 Correct 632 ms 4320 KB Output is correct
16 Correct 107 ms 980 KB Output is correct
17 Correct 115 ms 980 KB Output is correct
18 Correct 110 ms 980 KB Output is correct
19 Correct 117 ms 980 KB Output is correct
20 Correct 111 ms 1052 KB Output is correct
21 Incorrect 741 ms 3956 KB Output isn't correct
22 Halted 0 ms 0 KB -