| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 547873 |
2022-04-11T23:55:38 Z |
Olympia |
Boat (APIO16_boat) |
C++17 |
|
1556 ms |
4252 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 < grid.size(); i++) {
dp[0][i] = (grid[i].first >= points[0].first && grid[i].second <= points[0].second) * (points[0].second - points[0].first + 1);
}
for (int i = 1; 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--) {
pos += (grid[j].first >= points[k].first && grid[j].second <= points[k].second);
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:98: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]
98 | for (int i = 0; i < grid.size(); i++) {
| ~~^~~~~~~~~~~~~
boat.cpp:102: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]
102 | for (int j = 0; j < grid.size(); j++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1556 ms |
4252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1556 ms |
4252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1556 ms |
4252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
