Submission #245328

#	Time	Username	Problem	Language	Result	Execution time	Memory
245328		neihcr7j	Boat (APIO16_boat)	C++14	100 / 100	1004 ms	11128 KiB

boat

#include<bits/stdc++.h>

#define M 1000000007
#define maxn 502

using namespace std;
typedef long long ll;

inline ll norm(ll a) {
  return (a < 0 ? a + M : (a >= M ? a - M : a));
}

inline ll mul(ll a, ll b) {
  return a * b % M;
}

ll power(ll a, ll b) {
  if (b == 0) return 1;
  if (b&1) return mul(power(a, b - 1), a);
  ll t = power(a, b / 2);
  return mul(t, t);
}

ll gt[maxn * 2], igt[maxn * 2];

void precalc(){
  int n = 1000;

  gt[0] = 1;
  for (int i = 1; i <= n; ++i)
    gt[i] = mul(gt[i - 1], i);

  igt[n] = power(gt[n], M - 2);

  for (int i = n - 1; i >= 0; --i)
    igt[i] = mul(igt[i + 1], i + 1);
}

ll C(int n, int k) {
  return mul(mul(gt[n], igt[k]), igt[n - k]);
}


int n;

int l[maxn], r[maxn];
vector < pair < int, int > > seg;
vector < vector < int > > a;
vector < int > leng;

ll dp[maxn * 4][maxn], sumk[maxn * 4];

int main(){
  #define TASK "ABC"
 // freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  precalc();

  cin >> n;

  vector < int > ret;

  for (int i = 1; i <= n; ++i) {
    cin >> l[i] >> r[i];

    ret.push_back(l[i]);
    ret.push_back(r[i]);
  }

  sort(ret.begin(), ret.end());

  seg.push_back({ret[0], ret[0]});

  for (int i = 1; i < ret.size(); ++i)
    if (ret[i] != ret[i - 1]) {
      if (ret[i - 1] + 1 != ret[i])
        seg.push_back({ret[i - 1] + 1, ret[i] - 1});
      seg.push_back({ret[i], ret[i]});
    }

  a = vector < vector < int > >(seg.size(), vector < int >(0, 0));
  leng = vector < int > (seg.size(), 0);

  for (int i = 0; i < seg.size(); ++i) {
    for (int j = 1; j <= n; ++j)
      if (l[j] <= seg[i].first && seg[i].second <= r[j])
        a[i].push_back(j);
    leng[i] = seg[i].second - seg[i].first + 1;
  }

  ll ans = 0;

  sumk[0] = 1;

  for (int i = 0; i < seg.size(); ++i) {
    ll l = leng[i];

    vector < ll > c(a[i].size() + 1, 0), val(a[i].size() + 1, 0);

    c[0] = 1;

    for (int k = 1; k <= a[i].size(); ++k) {
      if (k <= l)
        c[k] = mul(mul(c[k - 1], l - k + 1), power(k, M - 2));

      for (int x = k; x > 0; --x)
        if (x <= l)
          val[k] = norm(val[k] + mul(c[x], C(k - 1, x - 1)));
    }

     int index = 0;

    for (int k = 0; k <= n; ++k) {

      if (i) sumk[k] = norm(sumk[k] + dp[i - 1][k]);

      ll res = sumk[k];

      while (index < a[i].size() && a[i][index] <= k)
        index++;

      for (int j = index; j < a[i].size(); ++j)
        dp[i][a[i][j]] = norm(dp[i][a[i][j]] + mul(res, val[j - index + 1]));

      ans = norm(ans + dp[i][k]);
    }
  }

  cout << ans;

  return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < ret.size(); ++i)
                   ~~^~~~~~~~~~~~
boat.cpp:85:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seg.size(); ++i) {
                   ~~^~~~~~~~~~~~
boat.cpp:96:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seg.size(); ++i) {
                   ~~^~~~~~~~~~~~
boat.cpp:103:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 1; k <= a[i].size(); ++k) {
                     ~~^~~~~~~~~~~~~~
boat.cpp:120:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (index < a[i].size() && a[i][index] <= k)
              ~~~~~~^~~~~~~~~~~~~
boat.cpp:123:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = index; j < a[i].size(); ++j)
                           ~~^~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42