Submission #549510

#	Time	Username	Problem	Language	Result	Execution time	Memory
549510		Jarif_Rahman	Misspelling (JOI22_misspelling)	C++17	57 / 100	4051 ms	171004 KiB

misspelling

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll md = 1000000007;

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

    int n, m; cin >> n >> m;
    vector<vector<int>> gr(n), lr(n);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b; a--, b--;
        if(a < b) lr[a].pb(b);
        else gr[b].pb(a);
    }

    vector<vector<ll>> dp(n, vector<ll>(26, 0));
    vector<ll> DP(n, 0);
    dp[n-1] = vector<ll>(26, 1);
    DP[n-1] = 26;

    set<int> ss;
    ss.insert(n-1);
    set<int> s1, s2;

    ll A[26], B[26];

    for(int i = n-2; i >= 0; i--){
        fill(A, A+26, 0);
        fill(B, B+26, 0);

        for(int x: gr[i]){
            auto it = ss.lower_bound(i);
            int a = -1;
            if(it != ss.end()) a = *it;
            while(it != ss.end() && *it <= x){
                s1.insert(*it);
                it = ss.erase(it);
            }
            it = s2.lower_bound(i);
            while(it != s2.end() && *it <= x){
                if(*it < (a==-1?n:a))
                    for(int j = 0; j < 26; j++) B[j]-=dp[*it][j], B[j]%=md;
                it = s2.erase(it);
            }
            if(a != -1){
                int b = n;
                if(!ss.empty()) b = *ss.begin();
                auto it = s1.lower_bound(a);
                while(it != s1.end() && *it < b){
                    for(int j = 0; j < 26; j++) A[j]+=dp[*it][j], A[j]%=md;
                    it++;
                }
                it = s2.lower_bound(a);
                while(it != s2.end() && *it < b){
                    for(int j = 0; j < 26; j++) B[j]+=dp[*it][j], B[j]%=md;
                    it++;
                }
            }
        }
        for(int x: lr[i]){
            auto it = ss.lower_bound(i);
            int a = -1;
            if(it != ss.end()) a = *it;
            while(it != ss.end() && *it <= x){
                s2.insert(*it);
                it = ss.erase(it);
            }
            it = s1.lower_bound(i);
            while(it != s1.end() && *it <= x){
                if(*it < (a==-1?n:a))
                    for(int j = 0; j < 26; j++) A[j]-=dp[*it][j], A[j]%=md;
                it = s1.erase(it);
            }
            if(a != -1){
                int b = n;
                if(!ss.empty()) b = *ss.begin();
                auto it = s1.lower_bound(a);
                while(it != s1.end() && *it < b){
                    for(int j = 0; j < 26; j++) A[j]+=dp[*it][j], A[j]%=md;
                    it++;
                }
                it = s2.lower_bound(a);
                while(it != s2.end() && *it < b){
                    for(int j = 0; j < 26; j++) B[j]+=dp[*it][j], B[j]%=md;
                    it++;
                }
            }
        }

        for(int j = 24; j >= 0; j--) A[j]+=A[j+1], A[j]%=md;
        for(int j = 1; j < 26; j++) B[j]+=B[j-1], B[j]%=md;

        for(int j = 0; j < 26; j++){
            if(j != 0) dp[i][j]+=B[j-1], dp[i][j]%=md;
            if(j != 25) dp[i][j]+=A[j+1], dp[i][j]%=md;
            if(ss.empty()) dp[i][j]++, dp[i][j]%=md;
            else dp[i][j]+=DP[*ss.begin()];
        }

        ss.insert(i);

        for(int j = 0; j < 26; j++) DP[i]+=dp[i][j], DP[i]%=md;

        if(DP[0] < 0) DP[0]+=md;
    }

    cout << DP[0] << "\n";
}

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