Submission #631551

#	Time	Username	Problem	Language	Result	Execution time	Memory
631551		alvingogo	Misspelling (JOI22_misspelling)	C++14	0 / 100	0 ms	212 KiB

misspelling

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

const int mod=1e9+7;
void add(int& x,int y){
    x+=y;
    x-=mod*(x>=mod);
}
int main(){
    AquA;
    int n;
    cin >> n;
    int m;
    cin >> m;
    vector<vector<int> > dc(n),ic(n),ddc(n+1),dic(n+1);
    vector<int> kd(n,-1),ki(n,-1);
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        if(a<b){
            dc[a].push_back(a);
            ddc[b+1].push_back(a);
        }
        else{
            ic[b].push_back(b);
            dic[a+1].push_back(b);
        }
    }
    multiset<int> s1,s2;
    for(int i=0;i<n;i++){
        for(auto h:ddc[i]){
            s1.erase(s1.find(h));
        }
        for(auto h:dic[i]){
            s2.erase(s2.find(h));
        }
        if(s1.size()){
            kd[i]=*s1.begin();
        }
        if(s2.size()){
            ki[i]=*s2.begin();
        }
        for(auto h:dc[i]){
            s1.insert(h);
        }
        for(auto h:ic[i]){
            s2.insert(h);
        }
    }
    vector<vector<int> > dp(n,vector<int>(26));
    vector<vector<int> > pre=dp,pp=dp;
    for(int i=0;i<26;i++){
        dp[0][i]=1;
        pre[0][i]=pre[0][(i>0)*(i-1)]+1;
        pp[0][i]=pre[0][i];
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<26;j++){
            if(j){
                int z=i-1;
                if(kd[i]>=0){
                    z=kd[i]-1;
                }
                add(dp[i][j],(z>=0?pp[z][j-1]:0));
            }
            if(j<25){
                int z=i-1;
                if(ki[i]>=0){
                    z=ki[i]-1;
                }
                add(dp[i][j],(z>=0?pp[z][25]-pp[z][j]:0));
            }
            add(pre[i][j],dp[i][j]);
            if(j){
                add(pre[i][j],pre[i][j-1]);
            }
            add(pp[i][j],pp[i-1][j]);
            add(pp[i][j],pre[i][j]);
        }
    }
    cout << pre[n-1][25] << "\n";
    return 0;
}

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