| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 969334 |
2024-04-25T02:17:45 Z |
MinaRagy06 |
Boat (APIO16_boat) |
C++17 |
|
2 ms |
1372 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
struct mint {
int v;
mint(long long x) {
if (x >= mod) x %= mod;
v = x;
}
mint() {v = 0;}
mint& operator+=(mint b) {
if ((v += b.v) >= mod) {
v -= mod;
}
return *this;
}
mint& operator-=(mint b) {
if ((v -= b.v) < 0) {
v += mod;
}
return *this;
}
mint& operator*=(mint b) {
v = 1ll * v * b.v % mod;
return *this;
}
mint power(mint a, int b) {
mint ans = 1;
while (b) {
if (b & 1) {
ans *= a;
}
a *= a, b >>= 1;
}
return ans;
}
mint& operator/=(mint b) {
v = 1ll * v * power(b, mod - 2).v % mod;
return *this;
}
friend mint operator+(mint a, mint b) {
return a += b;
}
friend mint operator-(mint a, mint b) {
return a -= b;
}
friend mint operator*(mint a, mint b) {
return a *= b;
}
friend mint operator/(mint a, mint b) {
return a /= b;
}
friend istream& operator>>(istream &is, mint &a) {
return is >> a.v;
}
friend ostream& operator<<(ostream &os, mint a) {
return os << a.v;
}
};
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
array<int, 2> a[n];
vector<int> v;
for (int i = 0; i < n; i++) {
cin >> a[i][0] >> a[i][1];
v.push_back(a[i][0]);
v.push_back(a[i][1]);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
auto get = [&] (int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin();
};
int m = v.size();
vector<int> gud[m];
for (int i = 0; i < n; i++) {
int l = get(a[i][0]), r = get(a[i][1]);
for (int j = l; j <= r; j++) {
gud[j].push_back(i + 1);
}
}
mint dp[m + 1][n + 1];
for (int j = 0; j <= n; j++) {
dp[m][j] = 1;
}
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j <= n; j++) {
dp[i][j] = dp[i + 1][j];
for (auto k : gud[i]) {
if (j <= k) {
dp[i][j] += dp[i + 1][k];
break;
}
}
}
}
cout << dp[0][0] - 1 << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1368 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1368 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1368 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1272 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1368 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1368 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1368 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1272 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1368 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1368 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1368 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1272 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
