Submission #712432

#	Time	Username	Problem	Language	Result	Execution time	Memory
712432		elkernos	Misspelling (JOI22_misspelling)	C++17	100 / 100	1081 ms	175152 KiB

misspelling

// clang-format off
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
~debug() { cerr << endl; }
eni(!=) cerr << "\x1b[1m\x1b[33m" << boolalpha << i << "\x1b[0m"; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; }
sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; }
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
struct { template <class T> operator T() { T x; cin >> x; return x; } } in;
#define endl '\n'
#define pb emplace_back
#define vt vector
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using i64 = long long;
// clang-format on

// clang-format off
template <class T>
T power(T a, i64 b) { T res = 1; for (; b; b /= 2, a *= a) if (b % 2) res *= a; return res; }
template <int P>
struct MInt {
    int x;
    MInt() : x{} {}
    MInt(i64 _x) : x{norm(_x % P)} {}
    int norm(int _x) const { if (_x < 0) _x += P; if (_x >= P) _x -= P; return _x; }
    int val() const { return x; }
    explicit operator int() const { return x; }
    MInt operator-() const { MInt res; res.x = norm(P - x); return res; }
    MInt inv() const { assert(x != 0); return power(*this, P - 2); }
    MInt &operator*=(MInt rhs) { x = (i64)x * rhs.x % P; return *this; }
    MInt &operator+=(MInt rhs) { x = norm(x + rhs.x); return *this; }
    MInt &operator-=(MInt rhs) { x = norm(x - rhs.x); return *this; }
    MInt &operator/=(MInt rhs) { return *this *= rhs.inv(); }
    friend MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; }
    friend MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; }
    friend MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; }
    friend MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; }
    friend istream &operator>>(istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; }
    friend ostream &operator<<(ostream &os, const MInt &a) { return os << a.val(); }
    friend bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
};
const int P = 1000*1000*1000+7;
using Z = MInt<P>;
// clang-format on

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n = in, m = in;
    vector<pair<int, int>> r(m);
    for (auto &[a, b] : r) {
        a = in, b = in;
        a--, b--;
    }
    vector<vector<int>> starts(n);
    for (int i = 0; i < m; i++)
        starts[min(r[i].first, r[i].second)].push_back(i);
    vector<vector<Z>> dp(n, vector<Z>(26)), prefdp(n + 1, vector<Z>(26));
    for (int i = 0; i < 26; i++)
        dp[0][i] = prefdp[0][i] = 1;
    priority_queue<pair<int, int>> inc, dec;
    for (int i = 1; i < n; i++) {
        for (auto j : starts[i - 1]) {
            auto [ai, bi] = r[j];
            if (ai > bi) inc.emplace(bi, ai);
            else dec.emplace(ai, bi);
        }
        while (sz(inc) && inc.top().second < i)
            inc.pop();
        while (sz(dec) && dec.top().second < i)
            dec.pop();
        int j_up = (!sz(inc) ? n : inc.top().first);
        int j_down = (!sz(dec) ? n : dec.top().first);
        for (int now = 0; now < 26; now++) {
            for (int old = 0; old < now; old++)
                dp[i][now] += prefdp[i - 1][old] - prefdp[j_down][old];
            for (int old = now + 1; old < 26; old++)
                dp[i][now] += prefdp[i - 1][old] - prefdp[j_up][old];
            prefdp[i][now] = prefdp[i - 1][now] + dp[i][now];
        }
    }
    Z ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 26; j++)
            ans += dp[i][j];
    cout << ans << endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11