/**
____ ____ ____ ____ ____ ____
||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;
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;
}
pair < int, int > con[maxm];
int fac[2][maxn];
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 ++)
{
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 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:75:9: warning: unused variable 'sm' [-Wunused-variable]
75 | int sm = 0, bg = 0;
| ^~
misspelling.cpp:75:17: warning: unused variable 'bg' [-Wunused-variable]
75 | int sm = 0, bg = 0;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
53968 KB |
Output is correct |
2 |
Correct |
11 ms |
53968 KB |
Output is correct |
3 |
Correct |
11 ms |
53852 KB |
Output is correct |
4 |
Correct |
11 ms |
53972 KB |
Output is correct |
5 |
Correct |
11 ms |
53960 KB |
Output is correct |
6 |
Correct |
11 ms |
53852 KB |
Output is correct |
7 |
Correct |
12 ms |
53960 KB |
Output is correct |
8 |
Correct |
13 ms |
53848 KB |
Output is correct |
9 |
Correct |
12 ms |
53964 KB |
Output is correct |
10 |
Correct |
12 ms |
53928 KB |
Output is correct |
11 |
Correct |
12 ms |
53848 KB |
Output is correct |
12 |
Correct |
11 ms |
51800 KB |
Output is correct |
13 |
Correct |
11 ms |
53852 KB |
Output is correct |
14 |
Correct |
12 ms |
53972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
53968 KB |
Output is correct |
2 |
Correct |
11 ms |
53968 KB |
Output is correct |
3 |
Correct |
11 ms |
53852 KB |
Output is correct |
4 |
Correct |
11 ms |
53972 KB |
Output is correct |
5 |
Correct |
11 ms |
53960 KB |
Output is correct |
6 |
Correct |
11 ms |
53852 KB |
Output is correct |
7 |
Correct |
12 ms |
53960 KB |
Output is correct |
8 |
Correct |
13 ms |
53848 KB |
Output is correct |
9 |
Correct |
12 ms |
53964 KB |
Output is correct |
10 |
Correct |
12 ms |
53928 KB |
Output is correct |
11 |
Correct |
12 ms |
53848 KB |
Output is correct |
12 |
Correct |
11 ms |
51800 KB |
Output is correct |
13 |
Correct |
11 ms |
53852 KB |
Output is correct |
14 |
Correct |
12 ms |
53972 KB |
Output is correct |
15 |
Correct |
12 ms |
51804 KB |
Output is correct |
16 |
Correct |
12 ms |
53852 KB |
Output is correct |
17 |
Correct |
12 ms |
53848 KB |
Output is correct |
18 |
Correct |
11 ms |
53852 KB |
Output is correct |
19 |
Correct |
12 ms |
53852 KB |
Output is correct |
20 |
Correct |
11 ms |
54108 KB |
Output is correct |
21 |
Correct |
11 ms |
54228 KB |
Output is correct |
22 |
Correct |
17 ms |
54108 KB |
Output is correct |
23 |
Correct |
12 ms |
51920 KB |
Output is correct |
24 |
Correct |
12 ms |
53852 KB |
Output is correct |
25 |
Correct |
12 ms |
53852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
53848 KB |
Output is correct |
2 |
Correct |
11 ms |
53964 KB |
Output is correct |
3 |
Correct |
11 ms |
53848 KB |
Output is correct |
4 |
Correct |
11 ms |
51800 KB |
Output is correct |
5 |
Execution timed out |
4065 ms |
116788 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
53968 KB |
Output is correct |
2 |
Correct |
11 ms |
53968 KB |
Output is correct |
3 |
Correct |
11 ms |
53852 KB |
Output is correct |
4 |
Correct |
11 ms |
53972 KB |
Output is correct |
5 |
Correct |
11 ms |
53960 KB |
Output is correct |
6 |
Correct |
11 ms |
53852 KB |
Output is correct |
7 |
Correct |
12 ms |
53960 KB |
Output is correct |
8 |
Correct |
13 ms |
53848 KB |
Output is correct |
9 |
Correct |
12 ms |
53964 KB |
Output is correct |
10 |
Correct |
12 ms |
53928 KB |
Output is correct |
11 |
Correct |
12 ms |
53848 KB |
Output is correct |
12 |
Correct |
11 ms |
51800 KB |
Output is correct |
13 |
Correct |
11 ms |
53852 KB |
Output is correct |
14 |
Correct |
12 ms |
53972 KB |
Output is correct |
15 |
Correct |
12 ms |
51804 KB |
Output is correct |
16 |
Correct |
12 ms |
53852 KB |
Output is correct |
17 |
Correct |
12 ms |
53848 KB |
Output is correct |
18 |
Correct |
11 ms |
53852 KB |
Output is correct |
19 |
Correct |
12 ms |
53852 KB |
Output is correct |
20 |
Correct |
11 ms |
54108 KB |
Output is correct |
21 |
Correct |
11 ms |
54228 KB |
Output is correct |
22 |
Correct |
17 ms |
54108 KB |
Output is correct |
23 |
Correct |
12 ms |
51920 KB |
Output is correct |
24 |
Correct |
12 ms |
53852 KB |
Output is correct |
25 |
Correct |
12 ms |
53852 KB |
Output is correct |
26 |
Correct |
149 ms |
59392 KB |
Output is correct |
27 |
Execution timed out |
4019 ms |
55644 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
53968 KB |
Output is correct |
2 |
Correct |
11 ms |
53968 KB |
Output is correct |
3 |
Correct |
11 ms |
53852 KB |
Output is correct |
4 |
Correct |
11 ms |
53972 KB |
Output is correct |
5 |
Correct |
11 ms |
53960 KB |
Output is correct |
6 |
Correct |
11 ms |
53852 KB |
Output is correct |
7 |
Correct |
12 ms |
53960 KB |
Output is correct |
8 |
Correct |
13 ms |
53848 KB |
Output is correct |
9 |
Correct |
12 ms |
53964 KB |
Output is correct |
10 |
Correct |
12 ms |
53928 KB |
Output is correct |
11 |
Correct |
12 ms |
53848 KB |
Output is correct |
12 |
Correct |
11 ms |
51800 KB |
Output is correct |
13 |
Correct |
11 ms |
53852 KB |
Output is correct |
14 |
Correct |
12 ms |
53972 KB |
Output is correct |
15 |
Correct |
12 ms |
51804 KB |
Output is correct |
16 |
Correct |
12 ms |
53852 KB |
Output is correct |
17 |
Correct |
12 ms |
53848 KB |
Output is correct |
18 |
Correct |
11 ms |
53852 KB |
Output is correct |
19 |
Correct |
12 ms |
53852 KB |
Output is correct |
20 |
Correct |
11 ms |
54108 KB |
Output is correct |
21 |
Correct |
11 ms |
54228 KB |
Output is correct |
22 |
Correct |
17 ms |
54108 KB |
Output is correct |
23 |
Correct |
12 ms |
51920 KB |
Output is correct |
24 |
Correct |
12 ms |
53852 KB |
Output is correct |
25 |
Correct |
12 ms |
53852 KB |
Output is correct |
26 |
Correct |
12 ms |
53848 KB |
Output is correct |
27 |
Correct |
11 ms |
53964 KB |
Output is correct |
28 |
Correct |
11 ms |
53848 KB |
Output is correct |
29 |
Correct |
11 ms |
51800 KB |
Output is correct |
30 |
Execution timed out |
4065 ms |
116788 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |