oj.uz

Submission #547877

# Submission time Handle Problem Language Result Execution time Memory
547877 2022-04-12T00:21:19 Z Olympia Boat (APIO16_boat) C++17
0 / 100
 265 ms 4300 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] * ((modint)j).pow()) * (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 263 ms 4248 KB Output is correct
2 Correct 249 ms 4256 KB Output is correct
3 Correct 246 ms 4252 KB Output is correct
4 Correct 265 ms 4252 KB Output is correct
5 Correct 244 ms 4172 KB Output is correct
6 Correct 157 ms 4172 KB Output is correct
7 Correct 170 ms 4252 KB Output is correct
8 Correct 160 ms 4300 KB Output is correct
9 Correct 166 ms 4252 KB Output is correct
10 Correct 165 ms 4252 KB Output is correct
11 Correct 183 ms 4252 KB Output is correct
12 Correct 157 ms 4220 KB Output is correct
13 Correct 162 ms 4172 KB Output is correct
14 Correct 172 ms 4220 KB Output is correct
15 Correct 157 ms 4256 KB Output is correct
16 Incorrect 51 ms 1004 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 4248 KB Output is correct
2 Correct 249 ms 4256 KB Output is correct
3 Correct 246 ms 4252 KB Output is correct
4 Correct 265 ms 4252 KB Output is correct
5 Correct 244 ms 4172 KB Output is correct
6 Correct 157 ms 4172 KB Output is correct
7 Correct 170 ms 4252 KB Output is correct
8 Correct 160 ms 4300 KB Output is correct
9 Correct 166 ms 4252 KB Output is correct
10 Correct 165 ms 4252 KB Output is correct
11 Correct 183 ms 4252 KB Output is correct
12 Correct 157 ms 4220 KB Output is correct
13 Correct 162 ms 4172 KB Output is correct
14 Correct 172 ms 4220 KB Output is correct
15 Correct 157 ms 4256 KB Output is correct
16 Incorrect 51 ms 1004 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 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 263 ms 4248 KB Output is correct
2 Correct 249 ms 4256 KB Output is correct
3 Correct 246 ms 4252 KB Output is correct
4 Correct 265 ms 4252 KB Output is correct
5 Correct 244 ms 4172 KB Output is correct
6 Correct 157 ms 4172 KB Output is correct
7 Correct 170 ms 4252 KB Output is correct
8 Correct 160 ms 4300 KB Output is correct
9 Correct 166 ms 4252 KB Output is correct
10 Correct 165 ms 4252 KB Output is correct
11 Correct 183 ms 4252 KB Output is correct
12 Correct 157 ms 4220 KB Output is correct
13 Correct 162 ms 4172 KB Output is correct
14 Correct 172 ms 4220 KB Output is correct
15 Correct 157 ms 4256 KB Output is correct
16 Incorrect 51 ms 1004 KB Output isn't correct
17 Halted 0 ms 0 KB -