#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;
constexpr int ALPHA = 26;
int add(int a, int b) {
return a + b < MOD ? a + b : a + b - MOD;
}
int sub(int a, int b) {
return a - b < 0 ? a - b + MOD : a - b;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N, M;
cin >> N >> M;
vector<int> A(M), B(M);
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i];
--A[i], --B[i];
}
vector<vector<int>> gt(N), lt(N);
for (int i = 0; i < M; i++) {
if (A[i] == B[i]) {
continue;
}
if (A[i] < B[i]) {
gt[A[i]].push_back(B[i]);
} else {
lt[B[i]].push_back(A[i]);
}
}
vector<vector<int>> DP(N, vector<int>(ALPHA));
vector<vector<int>> pref(N + 1, vector<int>(ALPHA + 1));
vector<vector<int>> suff(N + 1, vector<int>(ALPHA + 1));
for (int i = 0; i < ALPHA; i++) {
DP[0][i] = 1;
}
set<array<int, 2>> lt_left, lt_right, gt_left, gt_right;
for (int i = 0; i < N; i++) {
while (!lt_right.empty() && (*lt_right.begin())[0] < i) {
auto [r, l] = *lt_right.begin();
lt_right.erase(lt_right.begin());
lt_left.erase({l, r});
}
while (!gt_right.empty() && (*gt_right.begin())[0] < i) {
auto [r, l] = *gt_right.begin();
gt_right.erase(gt_right.begin());
gt_left.erase({l, r});
}
if (i > 0) {
int X = 1 + (lt_left.empty() ? -1 : (*lt_left.rbegin())[0]);
int Y = 1 + (gt_left.empty() ? -1 : (*gt_left.rbegin())[0]);
for (int ch = 0; ch < ALPHA; ch++) {
DP[i][ch] = add(DP[i][ch], sub(pref[i][ALPHA], pref[max(X, Y)][ALPHA]));
if (X < Y) {
DP[i][ch] = add(DP[i][ch], sub(pref[Y][ch], pref[X][ch]));
} else {
DP[i][ch] = add(DP[i][ch], sub(suff[X][ch + 1], suff[Y][ch + 1]));
}
}
}
for (int ch = ALPHA - 1; ch >= 0; ch--) {
suff[i + 1][ch] = add(suff[i + 1][ch + 1], add(sub(suff[i][ch], suff[i][ch + 1]), DP[i][ch]));
}
for (int ch = 0; ch < ALPHA; ch++) {
pref[i + 1][ch + 1] = add(pref[i + 1][ch], add(sub(pref[i][ch + 1], pref[i][ch]), DP[i][ch]));
}
for (int j : lt[i]) {
lt_left.insert({i, j});
lt_right.insert({j, i});
}
for (int j : gt[i]) {
gt_left.insert({i, j});
gt_right.insert({j, i});
}
}
int answer = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < ALPHA; j++) {
answer = add(answer, DP[i][j]);
}
}
cout << answer << "\n";
}
# | 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... |