oj.uz

Submission #631505

# Submission time Handle Problem Language Result Execution time Memory
631505 2022-08-18T08:00:59 Z abc864197532 Misspelling (JOI22_misspelling) C++17
100 / 100
 947 ms 231312 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    if (a.empty()) return o << "{}";
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
    vv (int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
    vv (int n, int m) : vector <vector <T>> (n, vector <T>(m)) {}
    vv () {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv (int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
    vvv (int n, int m, int k) : vector <vv <T>> (n, vv <T>(m, k)) {}
    vvv () {}
};
#ifdef Doludu
#define test(args...) abc("[" + string(#args) + "]", args)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(args...) void(0)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 1e9 + 7, N = 500002;

void add(int &i, int j) {
    i += j;
    if (i >= mod)
        i -= mod;
}

template <typename T>
struct SparseTableMax {
    // 0-indexed, [l, r)
    vector <vector <T>> table;
    SparseTableMax () = default;
    SparseTableMax (vector <T> a) {
        int n = a.size();
        int m = __lg(n) + 1;
        table.resize(n, vector <T> (m, 0));
        for (int i = 0; i < n; ++i)
            table[i][0] = a[i];
        for (int j = 1; j < m; ++j) {
            for (int i = 0; i + (1 << j) <= n; ++i) {
                table[i][j] = max(table[i][j - 1], table[i + (1 << j - 1)][j - 1]);
            }
        }
    }
    T query(int l, int r) {
        if (l >= r)
            return -1 << 30;
        int g = __lg(r - l);
        return max(table[l][g], table[r - (1 << g)][g]);
    }
};

int dp[N][29], pre[N][26];

void solve() {
    int n, m;
    cin >> n >> m;
    vector <int> mx1(n), mx2(n);
    auto add_edge = [&](int u, int v) {
        if (u < v)
            mx1[u] = max(mx1[u], v);
        else
            mx2[v] = max(mx2[v], u);
    };
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v, --u, --v;
        add_edge(u, v);
    }
    SparseTableMax <int> ST1(mx1), ST2(mx2);
    // s[i - 1] < s[i]
    for (int i = 0; i < 26; ++i)
        dp[0][i] = 1, pre[1][i] = 1;
    for (int i = 1; i < n; ++i) {
        // dp[i] -> dp[j];
        // s[i - 1] != s[i] -> only care range start from i

        // s[j - 1] < s[j]
        // no i -> j, i < j
        {
            int l = -1, r = i;
            while (r - l > 1) {
                int m = l + r >> 1;
                if (ST1.query(m, i) < i)
                    r = m;
                else
                    l = m;
            }
            int tmp = 0;
            for (int c = 0; c < 26; ++c) {
                add(dp[i][c], tmp);
                add(tmp, mod - pre[r][c]);
                add(tmp, pre[i][c]);
            }
        }

        // s[j - 1] > s[j]
        // no i -> j, i > j
        {
            int l = -1, r = i;
            while (r - l > 1) {
                int m = l + r >> 1;
                if (ST2.query(m, i) < i)
                    r = m;
                else
                    l = m;
            }
            int tmp = 0;
            for (int c = 25; ~c; --c) {
                add(dp[i][c], tmp);
                add(tmp, mod - pre[r][c]);
                add(tmp, pre[i][c]);
            }
        }

        for (int c = 0; c < 26; ++c)
            pre[i + 1][c] = pre[i][c], add(pre[i + 1][c], dp[i][c]);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) for (int c = 0; c < 26; ++c) {
        add(ans, dp[i][c]);
    }
    cout << ans << '\n';
}

int main () {
    owo;
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

Compilation message

misspelling.cpp: In function 'void solve()':
misspelling.cpp:110:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |                 int m = l + r >> 1;
      |                         ~~^~~
misspelling.cpp:129:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  129 |                 int m = l + r >> 1;
      |                         ~~^~~
misspelling.cpp: In instantiation of 'SparseTableMax<T>::SparseTableMax(std::vector<_Tp>) [with T = int]':
misspelling.cpp:97:33:   required from here
misspelling.cpp:69:70: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   69 |                 table[i][j] = max(table[i][j - 1], table[i + (1 << j - 1)][j - 1]);
      |                                                                    ~~^~~

Subtask #1
8.0 / 8.0

# 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 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 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 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# 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 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 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 340 KB Output is correct
14 Correct 0 ms 340 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 2 ms 340 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 384 KB Output is correct

Subtask #3
29.0 / 29.0

# 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 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 845 ms 231240 KB Output is correct
6 Correct 840 ms 231132 KB Output is correct
7 Correct 890 ms 231248 KB Output is correct
8 Correct 881 ms 231148 KB Output is correct
9 Correct 900 ms 231144 KB Output is correct
10 Correct 21 ms 8908 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 862 ms 231180 KB Output is correct

Subtask #4
32.0 / 32.0

# 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 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 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 340 KB Output is correct
14 Correct 0 ms 340 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 2 ms 340 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 384 KB Output is correct
26 Correct 25 ms 9020 KB Output is correct
27 Correct 24 ms 8948 KB Output is correct
28 Correct 26 ms 8968 KB Output is correct
29 Correct 27 ms 8904 KB Output is correct
30 Correct 22 ms 8880 KB Output is correct
31 Correct 101 ms 8920 KB Output is correct
32 Correct 20 ms 8860 KB Output is correct
33 Correct 20 ms 8912 KB Output is correct
34 Correct 26 ms 8884 KB Output is correct
35 Correct 95 ms 8916 KB Output is correct
36 Correct 18 ms 8916 KB Output is correct
37 Correct 20 ms 8932 KB Output is correct
38 Correct 19 ms 8860 KB Output is correct
39 Correct 18 ms 8916 KB Output is correct

Subtask #5
11.0 / 11.0

# 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 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 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 340 KB Output is correct
14 Correct 0 ms 340 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 2 ms 340 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 384 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 845 ms 231240 KB Output is correct
31 Correct 840 ms 231132 KB Output is correct
32 Correct 890 ms 231248 KB Output is correct
33 Correct 881 ms 231148 KB Output is correct
34 Correct 900 ms 231144 KB Output is correct
35 Correct 21 ms 8908 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 862 ms 231180 KB Output is correct
39 Correct 25 ms 9020 KB Output is correct
40 Correct 24 ms 8948 KB Output is correct
41 Correct 26 ms 8968 KB Output is correct
42 Correct 27 ms 8904 KB Output is correct
43 Correct 22 ms 8880 KB Output is correct
44 Correct 101 ms 8920 KB Output is correct
45 Correct 20 ms 8860 KB Output is correct
46 Correct 20 ms 8912 KB Output is correct
47 Correct 26 ms 8884 KB Output is correct
48 Correct 95 ms 8916 KB Output is correct
49 Correct 18 ms 8916 KB Output is correct
50 Correct 20 ms 8932 KB Output is correct
51 Correct 19 ms 8860 KB Output is correct
52 Correct 18 ms 8916 KB Output is correct
53 Correct 850 ms 231248 KB Output is correct
54 Correct 820 ms 231204 KB Output is correct
55 Correct 839 ms 231148 KB Output is correct
56 Correct 880 ms 231252 KB Output is correct
57 Correct 895 ms 231216 KB Output is correct
58 Correct 944 ms 231144 KB Output is correct
59 Correct 849 ms 231224 KB Output is correct
60 Correct 947 ms 231184 KB Output is correct
61 Correct 596 ms 231236 KB Output is correct
62 Correct 928 ms 231140 KB Output is correct
63 Correct 823 ms 231280 KB Output is correct
64 Correct 815 ms 231312 KB Output is correct