| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 883082 |
2023-12-04T13:26:58 Z |
KN200711 |
Boat (APIO16_boat) |
C++14 |
|
3 ms |
348 KB |
# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;
const ll MOD = 1e9 + 7;
vector<int> seg[1100];
int l[1100], r[1100], len[1100];
bool V[501];
int num;
ll pref[1100], ad[1100], inv[1100];
ll fast(ll a, int b) {
if(b == 0) return 1ll;
if(b == 1) return a;
ll K = fast(a, b / 2);
K *= K;
K %= MOD;
if(b&1) {
K *= a;
K %= MOD;
}
return K;
}
void build() {
inv[0] = 1;
for(int i=1;i<1100;i++) {
inv[i] = fast(i, MOD - 2);
}
}
void fx(ll &a, ll c, ll d) {
a *= c;
a %= MOD;
a *= d;
a %= MOD;
}
int main() {
build();
int N;
scanf("%d", &N);
vector< pair<int, int> > arr;
arr.clear();
for(int i=1;i<=N;i++) {
int a, b;
scanf("%d %d", &a, &b);
arr.push_back(make_pair(a, i));
arr.push_back(make_pair(b + 1, -i));
}
sort(arr.begin(), arr.end());
int lst;
for(int i=0;i<arr.size();i++) {
if(i > 0 && arr[i].fi != arr[i - 1].fi) {
l[num] = lst;
r[num] = arr[i].fi - 1;
len[num] = r[num] - l[num] + 1;
for(int k=1;k<=N;k++) {
if(V[k]) seg[num].push_back(k);
}
num++;
}
if(arr[i].se < 0) V[-arr[i].se] = 0;
else V[arr[i].se] = 1;
lst = arr[i].fi;
}
pref[0] = 1ll;
for(int i=0;i<num;i++) {
// cout<<l[i]<<" "<<r[i]<<endl;
for(int k=1;k<=N;k++) ad[k] = 0ll;
for(int k=1;k<=seg[i].size();k++) {
ll as = 0ll;
if(k == 1) {
as = len[i];
} else if(len[i] >= 2) {
ll v = 1ll;
fx(v, len[i], 1ll);
fx(v, len[i] - 1, 2ll);
for(int c=0;;c++) {
as += v;
as %= MOD;
if(len[i] < c + 2) break;
if(k < c + 2) break;
fx(v, len[i] - c - 2ll, c + 3ll);
fx(v, k - c - 2ll, 1ll);
}
}
for(int c=0;c+k-1<seg[i].size();c++) {
ll D = as * pref[seg[i][c] - 1];
D %= MOD;
ad[seg[i][c + k - 1]] += D;
ad[seg[i][c + k - 1]] %= MOD;
}
}
ll kp = 0ll;
for(int k = 1;k<=N;k++) {
// cout<<i<<" "<<k<<" "<<ad[k]<<endl;
kp += ad[k];
kp %= MOD;
pref[k] += kp;
pref[k] %= MOD;
}
}
ll ans = 0ll;
for(int i=1;i<=N;i++) {
ans += pref[i];
ans %= MOD;
}
printf("%lld\n", ans);
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:59:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i=0;i<arr.size();i++) {
| ~^~~~~~~~~~~
boat.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int k=1;k<=seg[i].size();k++) {
| ~^~~~~~~~~~~~~~~
boat.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int c=0;c+k-1<seg[i].size();c++) {
| ~~~~~^~~~~~~~~~~~~~
boat.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
boat.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
