oj.uz

Submission #547876

# Submission time Handle Problem Language Result Execution time Memory
547876 2022-04-12T00:18:32 Z Olympia Boat (APIO16_boat) C++17
0 / 100
 322 ms 4356 KB 
#include <cmath>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <cassert>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>

const int M = 1e9 + 7;
const int MOD = 1e9 + 7;
using namespace std;
int64_t binPow (int64_t x, int64_t y) {
    int64_t ans = 1, res = x;
    while (y) {
        if (y & 1) ans *= res, ans %= MOD;
        res *= res, res %= MOD, y /= 2;
    }
    return ans;
}
int64_t inv (int64_t x) {
    return binPow(x, MOD - 2);
}
struct modint {
    modint() : n(0) {}
    template <class T> modint(T n) { n %= M; if (n < 0) n += M; this->n = n; }

    modint & operator+=(const modint &r) { n += r.n; if (n >= M) n -= M; return *this; }
    modint & operator-=(const modint &r) { n -= r.n; if (n < 0) n += M; return *this; }
    modint & operator*=(const modint &r) { n = (int) ((long long) n * r.n % M); return *this; }

    modint & operator--() { if (--n == -1) n = M - 1; return *this; }
    modint & operator++() { if (++n == M) n = 0; return *this; }
    modint operator--(int) { modint t = *this; --*this; return t; }
    modint operator++(int) { modint t = *this; ++*this; return t; }

    modint operator-() const { return 0 - *this; }
    modint operator+() const { return *this; }

    modint pow(long long k = M - 2) const {
        modint f = *this, p = 1;
        while (k > 0) {
            if (k % 2 == 1) f *= p;
            p *= p, k /= 2;
        }
        return f;
    }

    int mod() const { return M; }

    friend modint operator+(modint l, const modint &r) { return l += r; }
    friend modint operator-(modint l, const modint &r) { return l -= r; }
    friend modint operator*(modint l, const modint &r) { return l *= r; }

    friend bool operator==(const modint &l, const modint &r) { return l.n == r.n; }
    friend bool operator!=(const modint &l, const modint &r) { return l.n != r.n; }

    friend ostream & operator<<(ostream &out, const modint &r) { return out << r.n; }

    int n;
};

vector<pair<int,int>> compress (vector<pair<int,int>> &vec) {
    set<int> s;
    for (auto& p: vec) {
        s.insert(p.first), s.insert(p.second);
    }
    vector<int> v; for (int i: s) v.push_back(i);
    vector<pair<int,int>> grids;
    for (int i = 0; i < v.size(); i++) {
        grids.emplace_back(v[i], v[i]);
        if (i + 1 != v.size() && v[i] + 1 <= v[i + 1] - 1) grids.emplace_back(v[i] + 1, v[i + 1] - 1);
    }
    return grids;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N; cin >> N;
    vector<pair<int,int>> points(N);
    for (int i = 0; i < N; i++) cin >> points[i].first >> points[i].second;
    vector<pair<int,int>> grid = compress(points);
    modint combo[grid.size()][N + 1];
    for (int i = 0; i < grid.size(); i++) {
        combo[i][0] = 1;
        for (int j = 1; j <= N; j++) {
            combo[i][j] = (combo[i][j - 1] * inv(j)) * (grid[i].second - grid[i].first - j + 2);
        }
        for (int j = grid[i].second - grid[i].first + 2; j <= N; j++) {
            combo[i][j] = 0;
        }
    }
    modint dp[N][grid.size()];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < grid.size(); j++) {
            dp[i][j] = (j == 0) ? 1 : dp[i][j - 1];
            int pos = 0;
            for (int k = i; k >= 0; k--) {
                if (grid[j].first >= points[k].first && grid[j].second <= points[k].second) {
                    pos ++;
                    dp[i][j] += (((k == 0 || j == 0) ? 1 : dp[k - 1][j - 1]) * combo[j][pos]);
                }
            }
        }
    }
    cout << dp[N - 1][grid.size() - 1] - 1;
}

Compilation message

boat.cpp: In function 'std::vector<std::pair<int, int> > compress(std::vector<std::pair<int, int> >&)':
boat.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
boat.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if (i + 1 != v.size() && v[i] + 1 <= v[i + 1] - 1) grids.emplace_back(v[i] + 1, v[i + 1] - 1);
      |             ~~~~~~^~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < grid.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
boat.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for (int j = 0; j < grid.size(); j++) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 4232 KB Output is correct
2 Correct 308 ms 4268 KB Output is correct
3 Correct 295 ms 4296 KB Output is correct
4 Correct 322 ms 4260 KB Output is correct
5 Correct 291 ms 4284 KB Output is correct
6 Correct 219 ms 4232 KB Output is correct
7 Correct 194 ms 4264 KB Output is correct
8 Correct 236 ms 4356 KB Output is correct
9 Correct 214 ms 4232 KB Output is correct
10 Correct 193 ms 4272 KB Output is correct
11 Correct 228 ms 4356 KB Output is correct
12 Correct 205 ms 4232 KB Output is correct
13 Correct 226 ms 4260 KB Output is correct
14 Correct 206 ms 4240 KB Output is correct
15 Correct 201 ms 4264 KB Output is correct
16 Incorrect 60 ms 1012 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 4232 KB Output is correct
2 Correct 308 ms 4268 KB Output is correct
3 Correct 295 ms 4296 KB Output is correct
4 Correct 322 ms 4260 KB Output is correct
5 Correct 291 ms 4284 KB Output is correct
6 Correct 219 ms 4232 KB Output is correct
7 Correct 194 ms 4264 KB Output is correct
8 Correct 236 ms 4356 KB Output is correct
9 Correct 214 ms 4232 KB Output is correct
10 Correct 193 ms 4272 KB Output is correct
11 Correct 228 ms 4356 KB Output is correct
12 Correct 205 ms 4232 KB Output is correct
13 Correct 226 ms 4260 KB Output is correct
14 Correct 206 ms 4240 KB Output is correct
15 Correct 201 ms 4264 KB Output is correct
16 Incorrect 60 ms 1012 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 4232 KB Output is correct
2 Correct 308 ms 4268 KB Output is correct
3 Correct 295 ms 4296 KB Output is correct
4 Correct 322 ms 4260 KB Output is correct
5 Correct 291 ms 4284 KB Output is correct
6 Correct 219 ms 4232 KB Output is correct
7 Correct 194 ms 4264 KB Output is correct
8 Correct 236 ms 4356 KB Output is correct
9 Correct 214 ms 4232 KB Output is correct
10 Correct 193 ms 4272 KB Output is correct
11 Correct 228 ms 4356 KB Output is correct
12 Correct 205 ms 4232 KB Output is correct
13 Correct 226 ms 4260 KB Output is correct
14 Correct 206 ms 4240 KB Output is correct
15 Correct 201 ms 4264 KB Output is correct
16 Incorrect 60 ms 1012 KB Output isn't correct
17 Halted 0 ms 0 KB -