#include <bits/stdc++.h>
#define int long long
using namespace std;
template <const int32_t MOD> struct ModInt {
int32_t x;
ModInt() : x(0) {}
ModInt(long long u) : x(u % MOD) {
if (x < 0)
x += MOD;
}
friend bool operator==(const ModInt &a, const ModInt &b) {
return a.x == b.x;
}
friend bool operator!=(const ModInt &a, const ModInt &b) {
return a.x != b.x;
}
friend bool operator<(const ModInt &a, const ModInt &b) { return a.x < b.x; }
friend bool operator>(const ModInt &a, const ModInt &b) { return a.x > b.x; }
friend bool operator<=(const ModInt &a, const ModInt &b) {
return a.x <= b.x;
}
friend bool operator>=(const ModInt &a, const ModInt &b) {
return a.x >= b.x;
}
static ModInt sign(long long k) {
return ((k & 1) ? ModInt(MOD - 1) : ModInt(1));
}
ModInt &operator+=(const ModInt &m) {
x += m.x;
if (x >= MOD)
x -= MOD;
return *this;
}
ModInt &operator-=(const ModInt &m) {
x -= m.x;
if (x < 0LL)
x += MOD;
return *this;
}
ModInt &operator*=(const ModInt &m) {
x = (1LL * x * m.x) % MOD;
return *this;
}
friend ModInt operator-(const ModInt &a) {
ModInt res(a);
if (res.x)
res.x = MOD - res.x;
return res;
}
friend ModInt operator+(const ModInt &a, const ModInt &b) {
return ModInt(a) += ModInt(b);
}
friend ModInt operator-(const ModInt &a, const ModInt &b) {
return ModInt(a) -= ModInt(b);
}
friend ModInt operator*(const ModInt &a, const ModInt &b) {
return ModInt(a) *= ModInt(b);
}
static long long fp(long long u, long long k) {
long long res = 1LL;
while (k > 0LL) {
if (k & 1LL)
res = (res * u) % MOD;
u = (u * u) % MOD;
k /= 2LL;
}
return res;
}
static constexpr int mod() { return MOD; }
ModInt fastpow(long long k) { return ModInt(fp(x, k)); }
ModInt inv() {
assert(x);
return ModInt(fp(x, MOD - 2));
}
ModInt &operator/=(const ModInt &m) { return *this *= ModInt(m).inv(); }
friend ModInt operator/(const ModInt &a, const ModInt &b) {
return ModInt(a) *= ModInt(b).inv();
}
friend ostream &operator<<(ostream &out, const ModInt &a) {
return out << a.x;
}
friend istream &operator>>(istream &in, ModInt &a) { return in >> a.x; }
};
const int MOD = 1e9 + 7;
using Mint = ModInt<MOD>;
struct Contrainte {
int L, R;
bool inc;
};
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int longueur, nbContraintes;
cin >> longueur >> nbContraintes;
vector<Contrainte> contraintes(nbContraintes);
for (int i = 0; i < nbContraintes; ++i) {
int A, B;
cin >> A >> B;
--A, --B;
if (A < B)
contraintes[i] = {A, B, false};
else
contraintes[i] = {B, A, true};
}
vector<vector<int>> startAt(longueur);
for (int i = 0; i < nbContraintes; ++i)
startAt[contraintes[i].L].push_back(i);
vector<array<Mint, 26>> dp(longueur);
vector<array<Mint, 26>> prefDp(longueur + 1);
for (int i = 0; i <= longueur; ++i)
prefDp[i].fill(0);
dp[0].fill(1);
for (int c = 0; c < 26; ++c)
prefDp[1][c] += 1;
priority_queue<pair<int, int>> pqInc, pqDec;
for (int i = 1; i < longueur; ++i) {
for (int iContrainte : startAt[i - 1]) {
if (contraintes[iContrainte].inc)
pqInc.emplace(contraintes[iContrainte].L, iContrainte);
else
pqDec.emplace(contraintes[iContrainte].L, iContrainte);
}
while (!pqInc.empty() and contraintes[pqInc.top().second].R < i)
pqInc.pop();
while (!pqDec.empty() and contraintes[pqDec.top().second].R < i)
pqDec.pop();
int LInc = pqInc.empty() ? -1 : pqInc.top().first,
LDec = pqDec.empty() ? -1 : pqDec.top().first;
for (int nxt = 0; nxt < 26; ++nxt) {
dp[i][nxt] = 0;
for (int old = 0; old < nxt; ++old)
dp[i][nxt] += prefDp[i][old] - prefDp[LDec + 1][old];
for (int old = nxt + 1; old < 26; ++old)
dp[i][nxt] += prefDp[i][old] - prefDp[LInc + 1][old];
prefDp[i + 1][nxt] = prefDp[i][nxt] + dp[i][nxt];
}
}
Mint ret = 0;
for (int i = 0; i < longueur; ++i)
ret += accumulate(dp[i].begin(), dp[i].end(), Mint(0));
cout << ret << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
3 ms |
1108 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
774 ms |
148292 KB |
Output is correct |
6 |
Correct |
810 ms |
154780 KB |
Output is correct |
7 |
Correct |
761 ms |
154716 KB |
Output is correct |
8 |
Correct |
833 ms |
155368 KB |
Output is correct |
9 |
Correct |
801 ms |
154816 KB |
Output is correct |
10 |
Correct |
46 ms |
6604 KB |
Output is correct |
11 |
Correct |
1 ms |
320 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
882 ms |
150588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
3 ms |
1108 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
46 ms |
6472 KB |
Output is correct |
27 |
Correct |
52 ms |
5768 KB |
Output is correct |
28 |
Correct |
50 ms |
5712 KB |
Output is correct |
29 |
Correct |
30 ms |
6260 KB |
Output is correct |
30 |
Correct |
31 ms |
6272 KB |
Output is correct |
31 |
Correct |
234 ms |
31516 KB |
Output is correct |
32 |
Correct |
31 ms |
6220 KB |
Output is correct |
33 |
Correct |
48 ms |
6240 KB |
Output is correct |
34 |
Correct |
37 ms |
6260 KB |
Output is correct |
35 |
Correct |
182 ms |
31464 KB |
Output is correct |
36 |
Correct |
34 ms |
4868 KB |
Output is correct |
37 |
Correct |
30 ms |
5864 KB |
Output is correct |
38 |
Correct |
27 ms |
5588 KB |
Output is correct |
39 |
Correct |
31 ms |
5260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
3 ms |
1108 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
256 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
774 ms |
148292 KB |
Output is correct |
31 |
Correct |
810 ms |
154780 KB |
Output is correct |
32 |
Correct |
761 ms |
154716 KB |
Output is correct |
33 |
Correct |
833 ms |
155368 KB |
Output is correct |
34 |
Correct |
801 ms |
154816 KB |
Output is correct |
35 |
Correct |
46 ms |
6604 KB |
Output is correct |
36 |
Correct |
1 ms |
320 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
882 ms |
150588 KB |
Output is correct |
39 |
Correct |
46 ms |
6472 KB |
Output is correct |
40 |
Correct |
52 ms |
5768 KB |
Output is correct |
41 |
Correct |
50 ms |
5712 KB |
Output is correct |
42 |
Correct |
30 ms |
6260 KB |
Output is correct |
43 |
Correct |
31 ms |
6272 KB |
Output is correct |
44 |
Correct |
234 ms |
31516 KB |
Output is correct |
45 |
Correct |
31 ms |
6220 KB |
Output is correct |
46 |
Correct |
48 ms |
6240 KB |
Output is correct |
47 |
Correct |
37 ms |
6260 KB |
Output is correct |
48 |
Correct |
182 ms |
31464 KB |
Output is correct |
49 |
Correct |
34 ms |
4868 KB |
Output is correct |
50 |
Correct |
30 ms |
5864 KB |
Output is correct |
51 |
Correct |
27 ms |
5588 KB |
Output is correct |
52 |
Correct |
31 ms |
5260 KB |
Output is correct |
53 |
Correct |
676 ms |
135168 KB |
Output is correct |
54 |
Correct |
1273 ms |
135064 KB |
Output is correct |
55 |
Correct |
864 ms |
151464 KB |
Output is correct |
56 |
Correct |
882 ms |
151500 KB |
Output is correct |
57 |
Correct |
841 ms |
155316 KB |
Output is correct |
58 |
Correct |
833 ms |
153436 KB |
Output is correct |
59 |
Correct |
739 ms |
155316 KB |
Output is correct |
60 |
Correct |
904 ms |
150240 KB |
Output is correct |
61 |
Correct |
865 ms |
113924 KB |
Output is correct |
62 |
Correct |
841 ms |
142060 KB |
Output is correct |
63 |
Correct |
740 ms |
132928 KB |
Output is correct |
64 |
Correct |
655 ms |
123916 KB |
Output is correct |