/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const ll mod = 1000000007;
const int maxm = 5e5 + 10;
const int maxn = 5e5 + 10;
int n, m;
ll dp[maxn][30];
ll fen[30][maxn];
void update(int idx, int pos, ll val)
{
for (int i = pos; i < maxn; i += (i & -i))
{
fen[idx][i] += val;
if (fen[idx][i] >= mod)
fen[idx][i] -= mod;
}
}
ll sum(int idx, int pos)
{
ll s = 0;
for (int i = pos; i > 0; i -= (i & -i))
{
s += fen[idx][i];
if (s >= mod)
s -= mod;
}
return s;
}
ll query(int idx, int l, int r)
{
ll val = sum(idx, r) - sum(idx, l - 1);
if (val < 0)
val += mod;
return val;
}
pair < int, int > con[maxm];
int fac[2][maxn];
ll temp[30];
vector < int > add[2][maxn], rem[2][maxn];
void solve()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++)
{
cin >> con[i].first >> con[i].second;
if (con[i].first < con[i].second)
{
add[0][con[i].first].push_back(con[i].first);
rem[0][con[i].second].push_back(con[i].first);
}
else if (con[i].first > con[i].second)
{
add[1][con[i].second].push_back(con[i].second);
rem[1][con[i].first].push_back(con[i].second);
}
}
int sm = 0, bg = 0;
multiset < int > act0, act1;
for (int i = 1; i < n; i ++)
{
for (int v : add[0][i])
act0.insert(v);
for (int v : rem[0][i])
act0.erase(act0.find(v));
for (int v : add[1][i])
act1.insert(v);
for (int v : rem[1][i])
act1.erase(act1.find(v));
if (!act0.empty())
fac[0][i] = *act0.rbegin();
if (!act1.empty())
fac[1][i] = *act1.rbegin();
}
for (int j = 0; j < 26; j ++)
{
dp[1][j] = 1;
}
for (int i = 1; i <= n - 1; i ++)
{
for (int j = 0; j < 26; j ++)
{
update(j, i, dp[i][j]);
}
int pt_big = n, pt_small = n;
pt_big = i - fac[1][i] + 1;
pt_small = i - fac[0][i] + 1;
///cout << i << " " << pt_big << " " << pt_small << endl;
/**for (int d = 1; d <= m; d ++)
{
if (con[d].first == con[d].second)
continue;
if (con[d].first < con[d].second)
{
if (con[d].first >= i + 1 || con[d].second < i + 1)
continue;
pt_small = min(pt_small, i - con[d].first + 1);
}
else
{
if (con[d].second >= i + 1 || con[d].first < i + 1)
continue;
pt_big = min(pt_big, i - con[d].second + 1);
}
}*/
///cout << i << " : " << pt_big << " : " << pt_small << endl;
for (int c = 0; c < 26; c ++)
{
temp[c] = query(c, i - pt_small + 2, i);
}
ll sum = 0;
for (int c = 0; c < 26; c ++)
{
dp[i + 1][c] += sum;
if (dp[i + 1][c] >= mod)
dp[i + 1][c] -= mod;
sum += temp[c];
if (sum >= mod)
sum -= mod;
}
for (int c = 0; c < 26; c ++)
{
temp[c] = query(c, i - pt_big + 2, i);
}
sum = 0;
for (int c = 25; c >= 0; c --)
{
dp[i + 1][c] += sum;
if (dp[i + 1][c] >= mod)
dp[i + 1][c] -= mod;
sum += temp[c];
if (sum >= mod)
sum -= mod;
}
/**for (int j = 1; j <= i; j ++)
{
if (j < pt_small)
{
ll sum = 0;
for (int c = 0; c < 26; c ++)
{
dp[i + 1][c] += sum;
if (dp[i + 1][c] >= mod)
dp[i + 1][c] -= mod;
sum += dp[i - j + 1][c];
if (sum >= mod)
sum -= mod;
}
}
if (j < pt_big)
{
ll sum = 0;
for (int c = 25; c >= 0; c --)
{
dp[i + 1][c] += sum;
if (dp[i + 1][c] >= mod)
dp[i + 1][c] -= mod;
sum += dp[i - j + 1][c];
if (sum >= mod)
sum -= mod;
}
}
}*/
///cout << small << " : " << big << endl;
}
ll ans = 0;
for (int i = 1; i <= n; i ++)
for (int c = 0; c < 26; c ++)
{
ans = ans + dp[i][c];
if (ans >= mod)
ans -= mod;
}
cout << ans << endl;
}
int main()
{
solve();
return 0;
}
Compilation message
misspelling.cpp: In function 'void solve()':
misspelling.cpp:84:9: warning: unused variable 'sm' [-Wunused-variable]
84 | int sm = 0, bg = 0;
| ^~
misspelling.cpp:84:17: warning: unused variable 'bg' [-Wunused-variable]
84 | int sm = 0, bg = 0;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
55128 KB |
Output is correct |
2 |
Correct |
11 ms |
55128 KB |
Output is correct |
3 |
Correct |
12 ms |
55128 KB |
Output is correct |
4 |
Correct |
12 ms |
55128 KB |
Output is correct |
5 |
Correct |
11 ms |
55128 KB |
Output is correct |
6 |
Correct |
12 ms |
55128 KB |
Output is correct |
7 |
Correct |
12 ms |
55128 KB |
Output is correct |
8 |
Correct |
12 ms |
55128 KB |
Output is correct |
9 |
Correct |
13 ms |
55128 KB |
Output is correct |
10 |
Correct |
12 ms |
55128 KB |
Output is correct |
11 |
Correct |
12 ms |
55128 KB |
Output is correct |
12 |
Correct |
11 ms |
53080 KB |
Output is correct |
13 |
Correct |
11 ms |
55128 KB |
Output is correct |
14 |
Correct |
12 ms |
55132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
55128 KB |
Output is correct |
2 |
Correct |
11 ms |
55128 KB |
Output is correct |
3 |
Correct |
12 ms |
55128 KB |
Output is correct |
4 |
Correct |
12 ms |
55128 KB |
Output is correct |
5 |
Correct |
11 ms |
55128 KB |
Output is correct |
6 |
Correct |
12 ms |
55128 KB |
Output is correct |
7 |
Correct |
12 ms |
55128 KB |
Output is correct |
8 |
Correct |
12 ms |
55128 KB |
Output is correct |
9 |
Correct |
13 ms |
55128 KB |
Output is correct |
10 |
Correct |
12 ms |
55128 KB |
Output is correct |
11 |
Correct |
12 ms |
55128 KB |
Output is correct |
12 |
Correct |
11 ms |
53080 KB |
Output is correct |
13 |
Correct |
11 ms |
55128 KB |
Output is correct |
14 |
Correct |
12 ms |
55132 KB |
Output is correct |
15 |
Correct |
12 ms |
53080 KB |
Output is correct |
16 |
Correct |
13 ms |
55236 KB |
Output is correct |
17 |
Correct |
12 ms |
55128 KB |
Output is correct |
18 |
Correct |
12 ms |
55132 KB |
Output is correct |
19 |
Correct |
12 ms |
55128 KB |
Output is correct |
20 |
Correct |
12 ms |
55128 KB |
Output is correct |
21 |
Correct |
12 ms |
55128 KB |
Output is correct |
22 |
Correct |
19 ms |
55640 KB |
Output is correct |
23 |
Correct |
12 ms |
53080 KB |
Output is correct |
24 |
Correct |
12 ms |
55128 KB |
Output is correct |
25 |
Correct |
14 ms |
55224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
55128 KB |
Output is correct |
2 |
Correct |
12 ms |
55128 KB |
Output is correct |
3 |
Correct |
12 ms |
55128 KB |
Output is correct |
4 |
Correct |
12 ms |
53084 KB |
Output is correct |
5 |
Correct |
1335 ms |
307420 KB |
Output is correct |
6 |
Correct |
1350 ms |
314080 KB |
Output is correct |
7 |
Correct |
1358 ms |
314224 KB |
Output is correct |
8 |
Correct |
1382 ms |
314136 KB |
Output is correct |
9 |
Correct |
1383 ms |
314032 KB |
Output is correct |
10 |
Correct |
62 ms |
64608 KB |
Output is correct |
11 |
Correct |
12 ms |
55128 KB |
Output is correct |
12 |
Correct |
12 ms |
55132 KB |
Output is correct |
13 |
Correct |
1838 ms |
325692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
55128 KB |
Output is correct |
2 |
Correct |
11 ms |
55128 KB |
Output is correct |
3 |
Correct |
12 ms |
55128 KB |
Output is correct |
4 |
Correct |
12 ms |
55128 KB |
Output is correct |
5 |
Correct |
11 ms |
55128 KB |
Output is correct |
6 |
Correct |
12 ms |
55128 KB |
Output is correct |
7 |
Correct |
12 ms |
55128 KB |
Output is correct |
8 |
Correct |
12 ms |
55128 KB |
Output is correct |
9 |
Correct |
13 ms |
55128 KB |
Output is correct |
10 |
Correct |
12 ms |
55128 KB |
Output is correct |
11 |
Correct |
12 ms |
55128 KB |
Output is correct |
12 |
Correct |
11 ms |
53080 KB |
Output is correct |
13 |
Correct |
11 ms |
55128 KB |
Output is correct |
14 |
Correct |
12 ms |
55132 KB |
Output is correct |
15 |
Correct |
12 ms |
53080 KB |
Output is correct |
16 |
Correct |
13 ms |
55236 KB |
Output is correct |
17 |
Correct |
12 ms |
55128 KB |
Output is correct |
18 |
Correct |
12 ms |
55132 KB |
Output is correct |
19 |
Correct |
12 ms |
55128 KB |
Output is correct |
20 |
Correct |
12 ms |
55128 KB |
Output is correct |
21 |
Correct |
12 ms |
55128 KB |
Output is correct |
22 |
Correct |
19 ms |
55640 KB |
Output is correct |
23 |
Correct |
12 ms |
53080 KB |
Output is correct |
24 |
Correct |
12 ms |
55128 KB |
Output is correct |
25 |
Correct |
14 ms |
55224 KB |
Output is correct |
26 |
Correct |
64 ms |
64372 KB |
Output is correct |
27 |
Correct |
53 ms |
61948 KB |
Output is correct |
28 |
Correct |
52 ms |
61916 KB |
Output is correct |
29 |
Correct |
64 ms |
64336 KB |
Output is correct |
30 |
Correct |
65 ms |
64312 KB |
Output is correct |
31 |
Correct |
404 ms |
75400 KB |
Output is correct |
32 |
Correct |
59 ms |
64504 KB |
Output is correct |
33 |
Correct |
61 ms |
64336 KB |
Output is correct |
34 |
Correct |
67 ms |
64592 KB |
Output is correct |
35 |
Correct |
536 ms |
85800 KB |
Output is correct |
36 |
Correct |
45 ms |
63344 KB |
Output is correct |
37 |
Correct |
62 ms |
64336 KB |
Output is correct |
38 |
Correct |
60 ms |
63824 KB |
Output is correct |
39 |
Correct |
60 ms |
63628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
55128 KB |
Output is correct |
2 |
Correct |
11 ms |
55128 KB |
Output is correct |
3 |
Correct |
12 ms |
55128 KB |
Output is correct |
4 |
Correct |
12 ms |
55128 KB |
Output is correct |
5 |
Correct |
11 ms |
55128 KB |
Output is correct |
6 |
Correct |
12 ms |
55128 KB |
Output is correct |
7 |
Correct |
12 ms |
55128 KB |
Output is correct |
8 |
Correct |
12 ms |
55128 KB |
Output is correct |
9 |
Correct |
13 ms |
55128 KB |
Output is correct |
10 |
Correct |
12 ms |
55128 KB |
Output is correct |
11 |
Correct |
12 ms |
55128 KB |
Output is correct |
12 |
Correct |
11 ms |
53080 KB |
Output is correct |
13 |
Correct |
11 ms |
55128 KB |
Output is correct |
14 |
Correct |
12 ms |
55132 KB |
Output is correct |
15 |
Correct |
12 ms |
53080 KB |
Output is correct |
16 |
Correct |
13 ms |
55236 KB |
Output is correct |
17 |
Correct |
12 ms |
55128 KB |
Output is correct |
18 |
Correct |
12 ms |
55132 KB |
Output is correct |
19 |
Correct |
12 ms |
55128 KB |
Output is correct |
20 |
Correct |
12 ms |
55128 KB |
Output is correct |
21 |
Correct |
12 ms |
55128 KB |
Output is correct |
22 |
Correct |
19 ms |
55640 KB |
Output is correct |
23 |
Correct |
12 ms |
53080 KB |
Output is correct |
24 |
Correct |
12 ms |
55128 KB |
Output is correct |
25 |
Correct |
14 ms |
55224 KB |
Output is correct |
26 |
Correct |
12 ms |
55128 KB |
Output is correct |
27 |
Correct |
12 ms |
55128 KB |
Output is correct |
28 |
Correct |
12 ms |
55128 KB |
Output is correct |
29 |
Correct |
12 ms |
53084 KB |
Output is correct |
30 |
Correct |
1335 ms |
307420 KB |
Output is correct |
31 |
Correct |
1350 ms |
314080 KB |
Output is correct |
32 |
Correct |
1358 ms |
314224 KB |
Output is correct |
33 |
Correct |
1382 ms |
314136 KB |
Output is correct |
34 |
Correct |
1383 ms |
314032 KB |
Output is correct |
35 |
Correct |
62 ms |
64608 KB |
Output is correct |
36 |
Correct |
12 ms |
55128 KB |
Output is correct |
37 |
Correct |
12 ms |
55132 KB |
Output is correct |
38 |
Correct |
1838 ms |
325692 KB |
Output is correct |
39 |
Correct |
64 ms |
64372 KB |
Output is correct |
40 |
Correct |
53 ms |
61948 KB |
Output is correct |
41 |
Correct |
52 ms |
61916 KB |
Output is correct |
42 |
Correct |
64 ms |
64336 KB |
Output is correct |
43 |
Correct |
65 ms |
64312 KB |
Output is correct |
44 |
Correct |
404 ms |
75400 KB |
Output is correct |
45 |
Correct |
59 ms |
64504 KB |
Output is correct |
46 |
Correct |
61 ms |
64336 KB |
Output is correct |
47 |
Correct |
67 ms |
64592 KB |
Output is correct |
48 |
Correct |
536 ms |
85800 KB |
Output is correct |
49 |
Correct |
45 ms |
63344 KB |
Output is correct |
50 |
Correct |
62 ms |
64336 KB |
Output is correct |
51 |
Correct |
60 ms |
63824 KB |
Output is correct |
52 |
Correct |
60 ms |
63628 KB |
Output is correct |
53 |
Correct |
1342 ms |
295596 KB |
Output is correct |
54 |
Correct |
1185 ms |
295860 KB |
Output is correct |
55 |
Correct |
1669 ms |
312980 KB |
Output is correct |
56 |
Correct |
1669 ms |
313372 KB |
Output is correct |
57 |
Correct |
1326 ms |
313980 KB |
Output is correct |
58 |
Correct |
1323 ms |
314092 KB |
Output is correct |
59 |
Correct |
1352 ms |
314052 KB |
Output is correct |
60 |
Correct |
1859 ms |
317536 KB |
Output is correct |
61 |
Correct |
815 ms |
272748 KB |
Output is correct |
62 |
Correct |
1643 ms |
308428 KB |
Output is correct |
63 |
Correct |
1399 ms |
297808 KB |
Output is correct |
64 |
Correct |
1231 ms |
286624 KB |
Output is correct |