#include <bits/stdc++.h>
using namespace std;
const int maxn = 500005;
const int mod = 1000000007;
const int maxlog = 19;
const int alf = 26;
int add(int a,int b)
{
return a+b >= mod ? a+b-mod : a+b;
}
int st1[maxlog][maxn],stn[maxlog][maxn];
int maxst[maxn];
int dp[2][alf][maxn];
int MAX1(int l,int r)
{
if(l > r)
return 0;
return max(st1[maxst[r-l+1]][l],st1[maxst[r-l+1]][r-(1<<maxst[r-l+1])+1]);
}
int MAXn(int l,int r)
{
if(l > r)
return 0;
return max(stn[maxst[r-l+1]][l],stn[maxst[r-l+1]][r-(1<<maxst[r-l+1])+1]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int tst = 0;
for(int i = 1;i < maxn;++i)
{
maxst[i] = tst;
if((1<<(tst+1)) <= i+1)
{
tst++;
}
}
int n,m;
cin >> n >> m;
vector<vector<int>> r1(n),rn(n);
for(int i = 0;i < m;++i)
{
int a,b;
cin >> a >> b;
a--;
b--;
if(a < b)
{
rn[a].push_back(b-1);
}
else
{
r1[b].push_back(a-1);
}
}
int maxr1[n],maxrn[n];
for(int j = n-1;j >= 0;--j)
{
maxr1[j] = j;
for(int u = 0;u < rn[j].size();++u)
{
maxr1[j] = max(maxr1[j],rn[j][u]+1);
maxr1[j] = max(maxr1[j],MAX1(j+1,rn[j][u]));
}
for(int y = 0;j+(1<<y) <= n;++y)
{
st1[y][j] = (y == 0 ? maxr1[j] : max(st1[y-1][j],st1[y-1][j+(1<<(y-1))]));
}
maxrn[j] = j;
for(int u = 0;u < r1[j].size();++u)
{
maxrn[j] = max(maxrn[j],r1[j][u]+1);
maxrn[j] = max(maxrn[j],MAXn(j+1,r1[j][u]));
}
for(int y = 0;j+(1<<y) <= n;++y)
{
stn[y][j] = (y == 0 ? maxrn[j] : max(stn[y-1][j],stn[y-1][j+(1<<(y-1))]));
}
// cout << maxr1[j] << ' ' << maxrn[j] << endl;
}
for(int j = n-1;j >= 0;--j)
{
for(int c = 0;c < alf;++c)
{
if(j == n-1)
{
dp[0][c][j] = 0;
dp[1][c][j] = 0;
}
else
{
if(maxr1[j] != j)
{
dp[1][c][j] = dp[1][c][maxr1[j]];
}
else
{
dp[1][c][j] = dp[1][c][j+1];
for(int h = c+1;h < alf;++h)
{
dp[1][c][j] = add(add(dp[1][c][j],dp[0][h][j+1]),dp[1][h][j+1] + 1);
}
}
if(maxrn[j] != j)
{
dp[0][c][j] = dp[0][c][maxrn[j]];
}
else
{
dp[0][c][j] = dp[0][c][j+1];
for(int h = 0;h < c;++h)
{
dp[0][c][j] = add(add(dp[0][c][j],dp[1][h][j+1]),dp[0][h][j+1] + 1);
}
}
}
}
}
int ans = 0;
for(int i = 0;i < alf;++i)
{
ans = add(add(ans,dp[0][i][0]),dp[1][i][0] + 1);
}
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |