oj.uz

Submission #558860

# Submission time Handle Problem Language Result Execution time Memory
558860 2022-05-08T19:35:05 Z Sweezy Boat (APIO16_boat) C++17
9 / 100
 1162 ms 13556 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define int long long
 
template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
  
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
 
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, s, n) for (int i = s; i < (n); ++i)
#define pb push_back
#define sz(a) (int) (a.size())
 
const int mod = 1e9 + 7;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n), b(n), cs;
  rep(i, n) {
    cin >> a[i] >> b[i];
    cs.pb(a[i]);
    cs.pb(b[i]);
  }
 
  sort(all(cs));
  cs.erase(unique(all(cs)), cs.end());
  map<int, int> mp;
  vector<int> l, r;
  rep(i, sz(cs)) {
    if ((i == 0 ? 0 : cs[i - 1]) + 1 <= cs[i] - 1) {
      l.pb((i == 0 ? 0 : cs[i - 1]) + 1);
      r.pb(cs[i] - 1);
    }
    mp[cs[i]] = sz(l);
    l.pb(cs[i]);
    r.pb(cs[i]);
  }
  rep(i, n) {
    a[i] = mp[a[i]];
    b[i] = mp[b[i]];
    // debug(a[i], b[i]);
  }

  auto add = [&] (int &a, int b) -> void {
    (a += b) %= mod;
  };
 
  auto mul = [&] (int a, int b) -> int {
    return a * b % mod;
  };
 
  auto binpow = [&] (int a, int n) -> int {
    int res = 1;
    while (n) {
      if (n % 2) {
        res = mul(res, a);
      }
      a = mul(a, a);
      n /= 2;
    }
    return res;
  };
 
  auto inv = [&] (int val) {
    return binpow(val, mod - 2);
  };
 
  vector<int> f(n + 1), rf(n + 1);
  f[0] = rf[0] = 1;
  reps(i, 1, n + 1) {
    f[i] = mul(f[i - 1], i);
    rf[i] = inv(f[i]);
  }
 
  auto choose = [&] (int n, int k) {
    int res = 1;
    reps(i, 1, k + 1) {
      res = mul(res, n - k + i);
    }
    return mul(res, rf[k]);
  };

  // [i]: 1
  // 0 0 0 0 0 1 7 1 3 1 0 0 
  // [i]: 2
  // 0 0 0 1 53 1 35 9 33 13 42 14 
  // [i]: 3
  // 0 1 24 1 1484 55 497 99 0 0 0 0 

  // [i, x, j, cnt]: 3 6 3 1
  // [dp[i][x]]: 399
  // [i, x, j, cnt]: 3 6 2 2
  // [dp[i][x]]: 441
  // [i, x, j, cnt]: 3 6 1 3
  // [dp[i][x]]: 497

  int segs = sz(l);
  vector<vector<int>> C(segs, vector<int> (n + 1));
  rep(seg, segs) {
    rep(i, n + 1) {
      C[seg][i] = choose(r[seg] - l[seg] + 1, i);
    }
    reps(i, 3, n + 1) {
      add(C[seg][i], C[seg][i - 1]);
    }
  }
 
  int answer = 0;
  vector<vector<int>> dp(n, vector<int> (segs));
  rep(i, n) {
    reps(seg, a[i], b[i] + 1) {
      int len = r[seg] - l[seg] + 1;
      int cnt = 0;
      for (int j = i; j >= 0; j--) {
        if (a[j] <= seg && seg <= b[j]) {
          cnt++;
          if (cnt > len) break;
          // debug(i, seg, j, len, cnt, C[seg][cnt], choose(len, cnt));
          if (j == 0 || seg == 0) {
            add(dp[i][seg], C[seg][cnt]);
          } else {
            add(dp[i][seg], mul(dp[j - 1][seg - 1], C[seg][cnt]));
          }
          // debug(dp[i][seg]);
        }
      }
    }
    // debug(i, dp[i]);
    reps(j, 1, segs) {
      add(dp[i][j], dp[i][j - 1]);
    }
    add(answer, dp[i][b[i]]);
    rep(j, segs) {
      add(dp[i][j], (i ? dp[i - 1][j] : 1));
    }
  }

  cout << answer;
}
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 8184 KB Output is correct
2 Correct 669 ms 8188 KB Output is correct
3 Correct 693 ms 8180 KB Output is correct
4 Correct 676 ms 8184 KB Output is correct
5 Correct 670 ms 8308 KB Output is correct
6 Correct 689 ms 8184 KB Output is correct
7 Correct 667 ms 8184 KB Output is correct
8 Correct 673 ms 8180 KB Output is correct
9 Correct 690 ms 8188 KB Output is correct
10 Correct 668 ms 8188 KB Output is correct
11 Correct 671 ms 8180 KB Output is correct
12 Correct 680 ms 8184 KB Output is correct
13 Correct 681 ms 8184 KB Output is correct
14 Correct 671 ms 8184 KB Output is correct
15 Correct 691 ms 8188 KB Output is correct
16 Correct 119 ms 1684 KB Output is correct
17 Correct 129 ms 1748 KB Output is correct
18 Correct 124 ms 1712 KB Output is correct
19 Correct 127 ms 1760 KB Output is correct
20 Correct 130 ms 1720 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 8184 KB Output is correct
2 Correct 669 ms 8188 KB Output is correct
3 Correct 693 ms 8180 KB Output is correct
4 Correct 676 ms 8184 KB Output is correct
5 Correct 670 ms 8308 KB Output is correct
6 Correct 689 ms 8184 KB Output is correct
7 Correct 667 ms 8184 KB Output is correct
8 Correct 673 ms 8180 KB Output is correct
9 Correct 690 ms 8188 KB Output is correct
10 Correct 668 ms 8188 KB Output is correct
11 Correct 671 ms 8180 KB Output is correct
12 Correct 680 ms 8184 KB Output is correct
13 Correct 681 ms 8184 KB Output is correct
14 Correct 671 ms 8184 KB Output is correct
15 Correct 691 ms 8188 KB Output is correct
16 Correct 119 ms 1684 KB Output is correct
17 Correct 129 ms 1748 KB Output is correct
18 Correct 124 ms 1712 KB Output is correct
19 Correct 127 ms 1760 KB Output is correct
20 Correct 130 ms 1720 KB Output is correct
21 Incorrect 1162 ms 13556 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 8184 KB Output is correct
2 Correct 669 ms 8188 KB Output is correct
3 Correct 693 ms 8180 KB Output is correct
4 Correct 676 ms 8184 KB Output is correct
5 Correct 670 ms 8308 KB Output is correct
6 Correct 689 ms 8184 KB Output is correct
7 Correct 667 ms 8184 KB Output is correct
8 Correct 673 ms 8180 KB Output is correct
9 Correct 690 ms 8188 KB Output is correct
10 Correct 668 ms 8188 KB Output is correct
11 Correct 671 ms 8180 KB Output is correct
12 Correct 680 ms 8184 KB Output is correct
13 Correct 681 ms 8184 KB Output is correct
14 Correct 671 ms 8184 KB Output is correct
15 Correct 691 ms 8188 KB Output is correct
16 Correct 119 ms 1684 KB Output is correct
17 Correct 129 ms 1748 KB Output is correct
18 Correct 124 ms 1712 KB Output is correct
19 Correct 127 ms 1760 KB Output is correct
20 Correct 130 ms 1720 KB Output is correct
21 Incorrect 1162 ms 13556 KB Output isn't correct
22 Halted 0 ms 0 KB -