#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MOD = 1e9 + 7;
int sum(int a, int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int sub(int a, int b) {
return a - b < 0 ? a - b + MOD : a - b;
}
void add(int &a, int b) {
if ((a += b) >= MOD) {
a -= MOD;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<pair<int, int>> queries[2];
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
queries[a > b].push_back(minmax(a, b));
}
vector<vector<array<int, 3>>> open(n + 1);
vector<int> close(n + 1);
vector<array<int, 4>> segments; //l, r, type, val
for (int t = 0; t < 2; ++t) {
vector<array<int, 3>> events; //cord, type, val
for (auto [x, y]: queries[t]) {
events.push_back({x, 1, -1});
events.push_back({y, -1, x});
}
sort(events.begin(), events.end());
multiset<int> st;
for (int i = 0; i + 1 < events.size(); ++i) {
if (events[i][2] == -1) {
st.insert(events[i][0]);
}
if (events[i][2] != -1) {
st.extract(events[i][2]);
}
if (!st.empty() && events[i][0] != events[i + 1][0]) {
segments.push_back({events[i][0], events[i + 1][0], t, *st.rbegin()});
}
}
}
for (auto [l, r, t, val]: segments) {
open[l].push_back({r, t, val});
close[r] |= 1 << t;
}
int val[2]{};
constexpr int A = 26;
vector dp(A, vector<int>(n + 1)), pref(dp);
auto rangeSum = [&](int c, int l, int r) {
return sub(pref[c][r], l == 0 ? 0 : pref[c][l - 1]);
};
int cnt[2]{};
for (int i = 1; i <= n; ++i) {
for (int t : {0, 1}) {
if (close[i - 1] >> t & 1) {
val[t] = 0;
cnt[t] -= 1;
}
}
for (auto [r, t, v]: open[i - 1]) {
assert(++cnt[t] == 1);
assert(val[t] <= v);
val[t] = v;
}
if (i > 1) {
for (int a = 0; a < A; ++a) {
for (int b = 0; b < A; ++b) {
if (a == b) {
continue;
}
add(dp[b][i - 1], rangeSum(a, val[a > b], i - 2));
}
}
} else {
for (int j = 0; j < A; ++j) {
dp[j][0] = 1;
}
}
for (int j = 0; j < A; ++j) {
pref[j][i - 1] = sum(dp[j][i - 1], i == 1 ? 0 : pref[j][i - 2]);
}
}
int ans = 0;
for (int c = 0; c < A; ++c) {
for (int i = 0; i <= n; ++i) {
add(ans, dp[c][i]);
}
}
cout << ans << '\n';
return 0;
}
Compilation message
misspelling.cpp: In function 'int main()':
misspelling.cpp:55:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 0; i + 1 < events.size(); ++i) {
| ~~~~~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
320 KB |
Output is correct |
14 |
Correct |
0 ms |
316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
320 KB |
Output is correct |
14 |
Correct |
0 ms |
316 KB |
Output is correct |
15 |
Correct |
1 ms |
312 KB |
Output is correct |
16 |
Correct |
2 ms |
320 KB |
Output is correct |
17 |
Correct |
2 ms |
316 KB |
Output is correct |
18 |
Correct |
2 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 |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
7 ms |
844 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
2562 ms |
151760 KB |
Output is correct |
6 |
Correct |
2523 ms |
151768 KB |
Output is correct |
7 |
Correct |
2534 ms |
151776 KB |
Output is correct |
8 |
Correct |
2505 ms |
151736 KB |
Output is correct |
9 |
Correct |
2550 ms |
151940 KB |
Output is correct |
10 |
Correct |
102 ms |
6340 KB |
Output is correct |
11 |
Correct |
2 ms |
316 KB |
Output is correct |
12 |
Correct |
0 ms |
320 KB |
Output is correct |
13 |
Correct |
2782 ms |
157120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
320 KB |
Output is correct |
14 |
Correct |
0 ms |
316 KB |
Output is correct |
15 |
Correct |
1 ms |
312 KB |
Output is correct |
16 |
Correct |
2 ms |
320 KB |
Output is correct |
17 |
Correct |
2 ms |
316 KB |
Output is correct |
18 |
Correct |
2 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 |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
7 ms |
844 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
104 ms |
6296 KB |
Output is correct |
27 |
Correct |
87 ms |
5884 KB |
Output is correct |
28 |
Correct |
86 ms |
5732 KB |
Output is correct |
29 |
Correct |
108 ms |
6356 KB |
Output is correct |
30 |
Correct |
107 ms |
6280 KB |
Output is correct |
31 |
Correct |
456 ms |
25992 KB |
Output is correct |
32 |
Correct |
102 ms |
6336 KB |
Output is correct |
33 |
Correct |
104 ms |
6304 KB |
Output is correct |
34 |
Correct |
106 ms |
6372 KB |
Output is correct |
35 |
Correct |
500 ms |
25716 KB |
Output is correct |
36 |
Correct |
67 ms |
5016 KB |
Output is correct |
37 |
Correct |
104 ms |
6132 KB |
Output is correct |
38 |
Correct |
102 ms |
5860 KB |
Output is correct |
39 |
Correct |
97 ms |
5524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
320 KB |
Output is correct |
14 |
Correct |
0 ms |
316 KB |
Output is correct |
15 |
Correct |
1 ms |
312 KB |
Output is correct |
16 |
Correct |
2 ms |
320 KB |
Output is correct |
17 |
Correct |
2 ms |
316 KB |
Output is correct |
18 |
Correct |
2 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 |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
7 ms |
844 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
2562 ms |
151760 KB |
Output is correct |
31 |
Correct |
2523 ms |
151768 KB |
Output is correct |
32 |
Correct |
2534 ms |
151776 KB |
Output is correct |
33 |
Correct |
2505 ms |
151736 KB |
Output is correct |
34 |
Correct |
2550 ms |
151940 KB |
Output is correct |
35 |
Correct |
102 ms |
6340 KB |
Output is correct |
36 |
Correct |
2 ms |
316 KB |
Output is correct |
37 |
Correct |
0 ms |
320 KB |
Output is correct |
38 |
Correct |
2782 ms |
157120 KB |
Output is correct |
39 |
Correct |
104 ms |
6296 KB |
Output is correct |
40 |
Correct |
87 ms |
5884 KB |
Output is correct |
41 |
Correct |
86 ms |
5732 KB |
Output is correct |
42 |
Correct |
108 ms |
6356 KB |
Output is correct |
43 |
Correct |
107 ms |
6280 KB |
Output is correct |
44 |
Correct |
456 ms |
25992 KB |
Output is correct |
45 |
Correct |
102 ms |
6336 KB |
Output is correct |
46 |
Correct |
104 ms |
6304 KB |
Output is correct |
47 |
Correct |
106 ms |
6372 KB |
Output is correct |
48 |
Correct |
500 ms |
25716 KB |
Output is correct |
49 |
Correct |
67 ms |
5016 KB |
Output is correct |
50 |
Correct |
104 ms |
6132 KB |
Output is correct |
51 |
Correct |
102 ms |
5860 KB |
Output is correct |
52 |
Correct |
97 ms |
5524 KB |
Output is correct |
53 |
Correct |
2555 ms |
138736 KB |
Output is correct |
54 |
Correct |
2192 ms |
139048 KB |
Output is correct |
55 |
Correct |
2778 ms |
152108 KB |
Output is correct |
56 |
Correct |
2736 ms |
152288 KB |
Output is correct |
57 |
Correct |
2543 ms |
151764 KB |
Output is correct |
58 |
Correct |
2535 ms |
151904 KB |
Output is correct |
59 |
Correct |
2536 ms |
151852 KB |
Output is correct |
60 |
Correct |
2764 ms |
151812 KB |
Output is correct |
61 |
Correct |
1769 ms |
115852 KB |
Output is correct |
62 |
Correct |
2640 ms |
146112 KB |
Output is correct |
63 |
Correct |
2532 ms |
139080 KB |
Output is correct |
64 |
Correct |
2422 ms |
130004 KB |
Output is correct |