//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 500005
#define maxc 26
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
ll dp[maxn][maxc],pref[maxn][maxc];
int lim[maxn][2];
vector<int> s1[maxn], s2[maxn];
void madd(ll &u, ll v) {
u = ((u + v) % mod + mod)%mod;
}
int main() {
io
int n, m;
cin >> n >> m;
multiset<int> v1, v2;
for (int i = 0;i < m;i++) {
int a, b;
cin >> a >> b;
if (a < b) {
s2[a].push_back(a);
s2[b].push_back(-a);
} else {
s1[b].push_back(b);
s1[a].push_back(-b);
}
}
for (int i = 1;i <= n;i++) {
for (auto j:s1[i]) {
if (j > 0) v1.insert(j);
else v1.erase(v1.find(-j));
}
for (auto j:s2[i]) {
if (j > 0) v2.insert(j);
else v2.erase(v2.find(-j));
}
if (v1.size()) lim[i][0] = *prev(v1.end());
if (v2.size()) lim[i][1] = *prev(v2.end());
}
for (int i = 0;i < maxc;i++) dp[0][i] = 1, pref[0][i] = i + 1;
for (int i = 1;i < n;i++) {
//debug(lim[i][0], lim[i][1]);
for (int j = 0;j < maxc;j++) {
if (j) {
madd(dp[i][j], (pref[i-1][j-1] - (lim[i][1] > 0 ? pref[lim[i][1]-1][j-1] : 0) + mod));
}
if (j < maxc - 1) {
madd(dp[i][j], pref[i-1][maxc-1] - pref[i-1][j] -
(lim[i][0] > 0 ? pref[lim[i][0]-1][maxc-1] - pref[lim[i][0]-1][j] : 0) + mod);
}
pref[i][j] = (dp[i][j] + (j ? pref[i][j-1] : 0))%mod;
}
//pary(dp[i], dp[i] + maxc);
for (int j = 0;j < maxc;j++) madd(pref[i][j], pref[i-1][j]);
}
ll ans = (pref[n-1][maxc-1]) %mod;
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23812 KB |
Output is correct |
3 |
Correct |
12 ms |
23764 KB |
Output is correct |
4 |
Correct |
12 ms |
23780 KB |
Output is correct |
5 |
Correct |
13 ms |
23784 KB |
Output is correct |
6 |
Correct |
12 ms |
23812 KB |
Output is correct |
7 |
Correct |
14 ms |
23764 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
13 ms |
23808 KB |
Output is correct |
10 |
Correct |
13 ms |
23812 KB |
Output is correct |
11 |
Correct |
12 ms |
23816 KB |
Output is correct |
12 |
Correct |
12 ms |
23820 KB |
Output is correct |
13 |
Correct |
12 ms |
23764 KB |
Output is correct |
14 |
Correct |
12 ms |
23764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23812 KB |
Output is correct |
3 |
Correct |
12 ms |
23764 KB |
Output is correct |
4 |
Correct |
12 ms |
23780 KB |
Output is correct |
5 |
Correct |
13 ms |
23784 KB |
Output is correct |
6 |
Correct |
12 ms |
23812 KB |
Output is correct |
7 |
Correct |
14 ms |
23764 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
13 ms |
23808 KB |
Output is correct |
10 |
Correct |
13 ms |
23812 KB |
Output is correct |
11 |
Correct |
12 ms |
23816 KB |
Output is correct |
12 |
Correct |
12 ms |
23820 KB |
Output is correct |
13 |
Correct |
12 ms |
23764 KB |
Output is correct |
14 |
Correct |
12 ms |
23764 KB |
Output is correct |
15 |
Correct |
14 ms |
23892 KB |
Output is correct |
16 |
Correct |
12 ms |
23892 KB |
Output is correct |
17 |
Correct |
14 ms |
23892 KB |
Output is correct |
18 |
Correct |
15 ms |
23892 KB |
Output is correct |
19 |
Correct |
15 ms |
23808 KB |
Output is correct |
20 |
Correct |
12 ms |
23892 KB |
Output is correct |
21 |
Correct |
12 ms |
23892 KB |
Output is correct |
22 |
Correct |
16 ms |
24276 KB |
Output is correct |
23 |
Correct |
12 ms |
23892 KB |
Output is correct |
24 |
Correct |
12 ms |
23812 KB |
Output is correct |
25 |
Correct |
15 ms |
23892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23812 KB |
Output is correct |
3 |
Correct |
12 ms |
23764 KB |
Output is correct |
4 |
Correct |
14 ms |
23764 KB |
Output is correct |
5 |
Correct |
503 ms |
253144 KB |
Output is correct |
6 |
Correct |
540 ms |
252956 KB |
Output is correct |
7 |
Correct |
534 ms |
253292 KB |
Output is correct |
8 |
Correct |
485 ms |
253116 KB |
Output is correct |
9 |
Correct |
499 ms |
253012 KB |
Output is correct |
10 |
Correct |
35 ms |
32908 KB |
Output is correct |
11 |
Correct |
16 ms |
23812 KB |
Output is correct |
12 |
Correct |
17 ms |
23784 KB |
Output is correct |
13 |
Correct |
1361 ms |
275548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23812 KB |
Output is correct |
3 |
Correct |
12 ms |
23764 KB |
Output is correct |
4 |
Correct |
12 ms |
23780 KB |
Output is correct |
5 |
Correct |
13 ms |
23784 KB |
Output is correct |
6 |
Correct |
12 ms |
23812 KB |
Output is correct |
7 |
Correct |
14 ms |
23764 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
13 ms |
23808 KB |
Output is correct |
10 |
Correct |
13 ms |
23812 KB |
Output is correct |
11 |
Correct |
12 ms |
23816 KB |
Output is correct |
12 |
Correct |
12 ms |
23820 KB |
Output is correct |
13 |
Correct |
12 ms |
23764 KB |
Output is correct |
14 |
Correct |
12 ms |
23764 KB |
Output is correct |
15 |
Correct |
14 ms |
23892 KB |
Output is correct |
16 |
Correct |
12 ms |
23892 KB |
Output is correct |
17 |
Correct |
14 ms |
23892 KB |
Output is correct |
18 |
Correct |
15 ms |
23892 KB |
Output is correct |
19 |
Correct |
15 ms |
23808 KB |
Output is correct |
20 |
Correct |
12 ms |
23892 KB |
Output is correct |
21 |
Correct |
12 ms |
23892 KB |
Output is correct |
22 |
Correct |
16 ms |
24276 KB |
Output is correct |
23 |
Correct |
12 ms |
23892 KB |
Output is correct |
24 |
Correct |
12 ms |
23812 KB |
Output is correct |
25 |
Correct |
15 ms |
23892 KB |
Output is correct |
26 |
Correct |
34 ms |
32936 KB |
Output is correct |
27 |
Correct |
37 ms |
32692 KB |
Output is correct |
28 |
Correct |
34 ms |
32764 KB |
Output is correct |
29 |
Correct |
46 ms |
33236 KB |
Output is correct |
30 |
Correct |
46 ms |
33312 KB |
Output is correct |
31 |
Correct |
407 ms |
44308 KB |
Output is correct |
32 |
Correct |
38 ms |
32932 KB |
Output is correct |
33 |
Correct |
44 ms |
32904 KB |
Output is correct |
34 |
Correct |
45 ms |
33576 KB |
Output is correct |
35 |
Correct |
780 ms |
54532 KB |
Output is correct |
36 |
Correct |
28 ms |
31872 KB |
Output is correct |
37 |
Correct |
44 ms |
33248 KB |
Output is correct |
38 |
Correct |
39 ms |
32852 KB |
Output is correct |
39 |
Correct |
38 ms |
32428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23812 KB |
Output is correct |
3 |
Correct |
12 ms |
23764 KB |
Output is correct |
4 |
Correct |
12 ms |
23780 KB |
Output is correct |
5 |
Correct |
13 ms |
23784 KB |
Output is correct |
6 |
Correct |
12 ms |
23812 KB |
Output is correct |
7 |
Correct |
14 ms |
23764 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
13 ms |
23808 KB |
Output is correct |
10 |
Correct |
13 ms |
23812 KB |
Output is correct |
11 |
Correct |
12 ms |
23816 KB |
Output is correct |
12 |
Correct |
12 ms |
23820 KB |
Output is correct |
13 |
Correct |
12 ms |
23764 KB |
Output is correct |
14 |
Correct |
12 ms |
23764 KB |
Output is correct |
15 |
Correct |
14 ms |
23892 KB |
Output is correct |
16 |
Correct |
12 ms |
23892 KB |
Output is correct |
17 |
Correct |
14 ms |
23892 KB |
Output is correct |
18 |
Correct |
15 ms |
23892 KB |
Output is correct |
19 |
Correct |
15 ms |
23808 KB |
Output is correct |
20 |
Correct |
12 ms |
23892 KB |
Output is correct |
21 |
Correct |
12 ms |
23892 KB |
Output is correct |
22 |
Correct |
16 ms |
24276 KB |
Output is correct |
23 |
Correct |
12 ms |
23892 KB |
Output is correct |
24 |
Correct |
12 ms |
23812 KB |
Output is correct |
25 |
Correct |
15 ms |
23892 KB |
Output is correct |
26 |
Correct |
13 ms |
23764 KB |
Output is correct |
27 |
Correct |
12 ms |
23812 KB |
Output is correct |
28 |
Correct |
12 ms |
23764 KB |
Output is correct |
29 |
Correct |
14 ms |
23764 KB |
Output is correct |
30 |
Correct |
503 ms |
253144 KB |
Output is correct |
31 |
Correct |
540 ms |
252956 KB |
Output is correct |
32 |
Correct |
534 ms |
253292 KB |
Output is correct |
33 |
Correct |
485 ms |
253116 KB |
Output is correct |
34 |
Correct |
499 ms |
253012 KB |
Output is correct |
35 |
Correct |
35 ms |
32908 KB |
Output is correct |
36 |
Correct |
16 ms |
23812 KB |
Output is correct |
37 |
Correct |
17 ms |
23784 KB |
Output is correct |
38 |
Correct |
1361 ms |
275548 KB |
Output is correct |
39 |
Correct |
34 ms |
32936 KB |
Output is correct |
40 |
Correct |
37 ms |
32692 KB |
Output is correct |
41 |
Correct |
34 ms |
32764 KB |
Output is correct |
42 |
Correct |
46 ms |
33236 KB |
Output is correct |
43 |
Correct |
46 ms |
33312 KB |
Output is correct |
44 |
Correct |
407 ms |
44308 KB |
Output is correct |
45 |
Correct |
38 ms |
32932 KB |
Output is correct |
46 |
Correct |
44 ms |
32904 KB |
Output is correct |
47 |
Correct |
45 ms |
33576 KB |
Output is correct |
48 |
Correct |
780 ms |
54532 KB |
Output is correct |
49 |
Correct |
28 ms |
31872 KB |
Output is correct |
50 |
Correct |
44 ms |
33248 KB |
Output is correct |
51 |
Correct |
39 ms |
32852 KB |
Output is correct |
52 |
Correct |
38 ms |
32428 KB |
Output is correct |
53 |
Correct |
663 ms |
249288 KB |
Output is correct |
54 |
Correct |
647 ms |
249236 KB |
Output is correct |
55 |
Correct |
998 ms |
262992 KB |
Output is correct |
56 |
Correct |
981 ms |
263048 KB |
Output is correct |
57 |
Correct |
522 ms |
253296 KB |
Output is correct |
58 |
Correct |
504 ms |
253536 KB |
Output is correct |
59 |
Correct |
498 ms |
253204 KB |
Output is correct |
60 |
Correct |
1259 ms |
269272 KB |
Output is correct |
61 |
Correct |
304 ms |
228420 KB |
Output is correct |
62 |
Correct |
1075 ms |
261452 KB |
Output is correct |
63 |
Correct |
740 ms |
252752 KB |
Output is correct |
64 |
Correct |
501 ms |
242720 KB |
Output is correct |