Submission #1134187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134187		mariaclara	Misspelling (JOI22_misspelling)	C++20	0 / 100	0 ms	324 KiB

misspelling

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 5e5+5;
const ll MOD = 1e9+7;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n, m;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    set<pii> MIN, MAX;

    while(m--) {
        int a, b;
        cin >> a >> b;

        if(a < b) MIN.insert({a, b-1}); // menor que o anterior
        else MAX.insert({b, a-1}); // maior que o anterior
    }

    ll dp[n][26][2][2];
    memset(dp, 0, sizeof(dp));

    for(int l = 0; l < 26; l++) dp[0][l][0][0] = 1;

    for(int i = 0; i < n-1; i++) {
        bool next_min = 0, next_max = 0, cover_min = 0, cover_max = 0;

        auto ptr = MIN.lower_bound({i+2, 0});
        if(ptr != MIN.begin()) {
            ptr--;
            if(ptr -> sc > i) cover_min = 1;
            if(ptr -> fr == i+1) next_min = 1;
        }

        ptr = MAX.lower_bound({i+2, 0});
        if(ptr != MAX.begin()) {
            ptr--;
            if(ptr -> sc > i) cover_max = 1;
            if(ptr -> fr == i+1) next_max = 1;
        }

        for(int l = 0; l < 26; l++) {
            if(next_min) {
                dp[i][l][1][0] += dp[i][l][0][0];
                dp[i][l][0][0] = 0;
                dp[i][l][1][1] += dp[i][l][0][1];
                dp[i][l][0][1] = 0;
            }
            
            if(next_max) {
                dp[i][l][0][1] += dp[i][l][0][0];
                dp[i][l][0][0] = 0;
                dp[i][l][1][1] += dp[i][l][1][0];
                dp[i][l][1][0] = 0;
            }
             
            if(!cover_min) {
                dp[i][l][0][0] += dp[i][l][1][0];
                dp[i][l][1][0] = 0;
                dp[i][l][0][1] += dp[i][l][1][1];
                dp[i][l][1][1] = 0;
            }

            if(!cover_max) {
                dp[i][l][0][0] += dp[i][l][0][1];
                dp[i][l][0][1] = 0;
                dp[i][l][1][0] += dp[i][l][1][1];
                dp[i][l][1][1] = 0;
            }

            for(int next_l = 0; next_l < 26; next_l++) {
                dp[i+1][next_l][0][0] += dp[i][l][0][0] + dp[i][l][1][0] * (next_l < l) + dp[i][l][0][1] * (next_l > l);
                dp[i+1][next_l][1][0] += dp[i][l][1][0] * (next_l == l);
                dp[i+1][next_l][0][1] += dp[i][l][0][1] * (next_l == l);
                dp[i+1][next_l][1][1] += dp[i][l][1][1] * (next_l == l);
                
                dp[i+1][next_l][0][0] %= MOD;
                dp[i+1][next_l][0][1] %= MOD;
                dp[i+1][next_l][1][0] %= MOD;
                dp[i+1][next_l][1][1] %= MOD;
            }
        }
    }


    ll ans = 0;
    for(int l = 0; l < 26; l++) {
        ans = (ans + dp[n-1][l][0][0])%MOD;
        ans = (ans + dp[n-1][l][0][1])%MOD;
        ans = (ans + dp[n-1][l][1][0])%MOD;
        ans = (ans + dp[n-1][l][1][1])%MOD;
    }

    cout << ans << "\n";
}

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