#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;
struct DPValueList {
vector<pair<int, ll>> values;
ll sum;
DPValueList() : sum(0) {}
void reg(int i, ll v) {
sum = (sum + v) % MOD;
values.emplace_back(i, v);
}
void prune(int i) {
while (!values.empty() && values.back().first < i) {
sum = (sum + MOD - values.back().second) % MOD;
values.pop_back();
}
}
};
int main() {
int n, m; scanf("%d %d", &n, &m);
vector<vector<int>> firstIncEnds(n), firstDecEnds(n);
for (int i = 0; i < m; ++i) {
int a, b; scanf("%d %d", &a, &b); --a; --b;
// a < b means first change is an increase
if (a < b) firstDecEnds[a].push_back(b);
else firstIncEnds[b].push_back(a);
}
// simplify the constraints
for (int i = 0; i < n; ++i) {
if (firstIncEnds[i].size() > 0) {
firstIncEnds[i] = {*max_element(begin(firstIncEnds[i]), end(firstIncEnds[i]))};
}
if (firstDecEnds[i].size() > 0) {
firstDecEnds[i] = {*max_element(begin(firstDecEnds[i]), end(firstDecEnds[i]))};
}
if (firstIncEnds[i].size() > 0 && firstDecEnds[i].size() > 0) {
int first = min(firstIncEnds[i][0], firstDecEnds[i][0]), secnd = max(firstIncEnds[i][0], firstDecEnds[i][0]);
if (first < secnd) {
if (firstIncEnds[i][0] == secnd) firstIncEnds[first].push_back(secnd);
if (firstDecEnds[i][0] == secnd) firstDecEnds[first].push_back(secnd);
firstIncEnds[i][0] = firstDecEnds[i][0] = first;
}
}
}
//vector<vector<ll>> lastInc(n, vector<ll>(26)), lastDec(n, vector<ll>(26));
vector<DPValueList> lastInc(26), lastDec(26);
for (int i = 0; i < 26; ++i) lastInc[i].reg(n-1, 1);
for (int i = n - 2; i >= 0; --i) {
// count the current sols
vector<ll> currEndAt(26);
for (int d = 0; d < 26; ++d) {
currEndAt[d] += lastInc[d].sum + lastDec[d].sum;
currEndAt[d] %= MOD;
}
// update the counts for n
for (int d = 0; d < 26; ++d) {
ll curLastInc = 0, curLastDec = 0;
for (int dnext = 0; dnext < 26; ++dnext) {
if (d < dnext && firstDecEnds[i].size() == 0) { // increase
curLastInc += currEndAt[dnext];
}
if (d > dnext && firstIncEnds[i].size() == 0) { // decrease
curLastDec += currEndAt[dnext];
}
}
lastInc[d].reg(i, curLastInc % MOD);
lastDec[d].reg(i, curLastDec % MOD);
}
// eliminate all sols that don't follow any existing constraints
if (firstIncEnds[i].size() > 0) {
// printf("constraint first inc %d %d\n", i, firstIncEnds[i][0]);
for (int d = 0; d < 26; ++d) {
lastDec[d].prune(firstIncEnds[i][0]);
}
}
if (firstDecEnds[i].size() > 0) {
// printf("constraint first dec %d %d\n", i, firstDecEnds[i][0]);
for (int d = 0; d < 26; ++d) {
lastInc[d].prune(firstDecEnds[i][0]);
}
}
for (int d = 0; d < 26; ++d) {
// printf("%d %d inc %lld dec %lld\n", i, d, lastInc[i][d], lastDec[i][d]);
}
}
ll ans = 0;
for (int d = 0; d < 26; ++d) {
ans = (ans + lastInc[d].sum + lastDec[d].sum) % MOD;
}
printf("%lld\n", ans);
}
Compilation message
misspelling.cpp: In function 'int main()':
misspelling.cpp:24:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | int n, m; scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
misspelling.cpp:27:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | int a, b; scanf("%d %d", &a, &b); --a; --b;
| ~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
300 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
300 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
296 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
300 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
436 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
887 ms |
48928 KB |
Output is correct |
6 |
Correct |
951 ms |
50192 KB |
Output is correct |
7 |
Correct |
872 ms |
57220 KB |
Output is correct |
8 |
Correct |
950 ms |
51144 KB |
Output is correct |
9 |
Correct |
882 ms |
55608 KB |
Output is correct |
10 |
Correct |
41 ms |
2108 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1167 ms |
61668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
300 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
296 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
300 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
436 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
49 ms |
2092 KB |
Output is correct |
27 |
Correct |
42 ms |
10552 KB |
Output is correct |
28 |
Correct |
54 ms |
10792 KB |
Output is correct |
29 |
Correct |
40 ms |
2260 KB |
Output is correct |
30 |
Correct |
37 ms |
2260 KB |
Output is correct |
31 |
Correct |
140 ms |
10148 KB |
Output is correct |
32 |
Correct |
39 ms |
2168 KB |
Output is correct |
33 |
Correct |
36 ms |
2260 KB |
Output is correct |
34 |
Correct |
53 ms |
2132 KB |
Output is correct |
35 |
Correct |
170 ms |
10484 KB |
Output is correct |
36 |
Correct |
45 ms |
18412 KB |
Output is correct |
37 |
Correct |
38 ms |
2004 KB |
Output is correct |
38 |
Correct |
40 ms |
1948 KB |
Output is correct |
39 |
Correct |
38 ms |
2004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
300 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
296 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
300 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
436 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
300 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
887 ms |
48928 KB |
Output is correct |
31 |
Correct |
951 ms |
50192 KB |
Output is correct |
32 |
Correct |
872 ms |
57220 KB |
Output is correct |
33 |
Correct |
950 ms |
51144 KB |
Output is correct |
34 |
Correct |
882 ms |
55608 KB |
Output is correct |
35 |
Correct |
41 ms |
2108 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
1167 ms |
61668 KB |
Output is correct |
39 |
Correct |
49 ms |
2092 KB |
Output is correct |
40 |
Correct |
42 ms |
10552 KB |
Output is correct |
41 |
Correct |
54 ms |
10792 KB |
Output is correct |
42 |
Correct |
40 ms |
2260 KB |
Output is correct |
43 |
Correct |
37 ms |
2260 KB |
Output is correct |
44 |
Correct |
140 ms |
10148 KB |
Output is correct |
45 |
Correct |
39 ms |
2168 KB |
Output is correct |
46 |
Correct |
36 ms |
2260 KB |
Output is correct |
47 |
Correct |
53 ms |
2132 KB |
Output is correct |
48 |
Correct |
170 ms |
10484 KB |
Output is correct |
49 |
Correct |
45 ms |
18412 KB |
Output is correct |
50 |
Correct |
38 ms |
2004 KB |
Output is correct |
51 |
Correct |
40 ms |
1948 KB |
Output is correct |
52 |
Correct |
38 ms |
2004 KB |
Output is correct |
53 |
Correct |
975 ms |
49696 KB |
Output is correct |
54 |
Correct |
962 ms |
240232 KB |
Output is correct |
55 |
Correct |
1029 ms |
47832 KB |
Output is correct |
56 |
Correct |
1028 ms |
47692 KB |
Output is correct |
57 |
Correct |
976 ms |
46728 KB |
Output is correct |
58 |
Correct |
883 ms |
51532 KB |
Output is correct |
59 |
Correct |
886 ms |
51184 KB |
Output is correct |
60 |
Correct |
1117 ms |
44936 KB |
Output is correct |
61 |
Correct |
1109 ms |
413096 KB |
Output is correct |
62 |
Correct |
1051 ms |
40864 KB |
Output is correct |
63 |
Correct |
1059 ms |
36224 KB |
Output is correct |
64 |
Correct |
1014 ms |
32256 KB |
Output is correct |