Submission #1256579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256579		Bahamin	Misspelling (JOI22_misspelling)	C++20	100 / 100	517 ms	94348 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

inline int md(ll x) {x %= MOD; return x + (x < 0 ? MOD : 0);}
inline int ADD(ll a, ll b) {return md(a + b);}
inline int SUB(ll a, ll b) {return md(a - b);}
inline int MUL(ll a, ll b) {return md(1ll * a * b);}
inline int POW(ll a, ll b) {int res = 1; while (b){if (b & 1) res = MUL(res, a); a = MUL(a, a); b >>= 1;} return res;}
inline int DIV(ll a, ll b) {return MUL(a, POW(b, MOD - 2));}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, bool>> st[n];
    int dp[n][26];
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        bool ok = false;
        if (a > b) swap(a, b), ok = true;
        st[a].push_back(make_pair(b, ok));
    }
    int sum1[26];
    int sum2[26];
    int sum3[26];  
    fill(sum1, sum1 + 26, 0);
    fill(sum2, sum2 + 26, 0);
    fill(sum3, sum3 + 26, 0);
    set<int> s1;
    set<int> s2;
    set<int> s3;
    for (int i = n - 1; i >= 0; i--)
    {
        for (auto x : st[i]) 
        {
            if (x.second)
            {
                while (true)
                {
                    auto xx = s2.upper_bound(i);
                    if (xx != s2.end() && (*xx) <= x.first) 
                    {
                        int sum = 0;
                        for (int j = 0; j < 26; j++) sum2[j] = SUB(sum2[j], sum), sum = ADD(sum, dp[*xx][j]);
                        s2.erase(xx);
                    } else break;
                }
            } else 
            {
                while (true)
                {
                    auto xx = s3.upper_bound(i);
                    if (xx != s3.end() && (*xx) <= x.first) 
                    {
                        int sum = 0;
                        for (int j = 25; j >= 0; j--) sum3[j] = SUB(sum3[j], sum), sum = ADD(sum, dp[*xx][j]);
                        s3.erase(xx);
                    } else break;
                }
            }
            while (true)
            {
                auto xx = s1.upper_bound(i);
                if (xx != s1.end() && (*xx) <= x.first)
                {
                    if (!x.second)
                    {
                        int sum = 0;
                        for (int j = 0; j < 26; j++) sum2[j] = ADD(sum2[j], sum), sum = ADD(sum, dp[*xx][j]);
                        for (int j = 0; j < 26; j++) sum1[j] = SUB(sum1[j], SUB(sum, dp[*xx][j]));
                        s2.insert(*xx);
                        s1.erase(xx);
                    } else 
                    {
                        int sum = 0;
                        for (int j = 25; j >= 0; j--) sum3[j] = ADD(sum3[j], sum), sum = ADD(sum, dp[*xx][j]);
                        for (int j = 0; j < 26; j++) sum1[j] = SUB(sum1[j], SUB(sum, dp[*xx][j]));
                        s3.insert(*xx);
                        s1.erase(xx);
                    }
                } else break;
            }
        }   
        for (int j = 0; j < 26; j++) dp[i][j] = ADD(1, ADD(sum1[j], ADD(sum2[j], sum3[j])));
        s1.insert(i);
        int sum = 0;
        for (int j = 0; j < 26; j++) sum = ADD(sum, dp[i][j]);
        for (int j = 0; j < 26; j++) sum1[j] = ADD(sum1[j], SUB(sum, dp[i][j]));
    }
    int ans = 0;
    for (int i = 0; i < 26; i++) ans = ADD(ans, dp[0][i]);
    cout << ans << "\n";
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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