Submission #814774

#	Time	Username	Problem	Language	Result	Execution time	Memory
814774		jajco	Misspelling (JOI22_misspelling)	C++17	100 / 100	438 ms	154560 KiB

misspelling

#include <ios>
#include <queue>
#include <vector>
#define MOD 1000000007
typedef long long ll;
typedef std::vector <int> vi;
typedef std::vector <ll> vll;
struct prz{
    int p,k;
    bool operator<(const prz &i) const{
        return p<i.p;
    }
};
void DOD(ll &i, const ll j){
    if ((i+=j)>=MOD)
        i-=MOD;
}
int main(){
    int n;
    scanf("%d", &n);
    std::vector <vi> mkonv(n+1, vi()),wkonv(n+1, vi());
    { // wejscie
        int m;
        scanf("%d", &m);
        while (m--){
            int p,k;
            scanf("%d%d", &p, &k);
            if (p<k) // (i+1, j) <= (i, j-1); wlasciwie to
                mkonv[p].emplace_back(k); // bez znaczenia w/m
            else
                wkonv[k].emplace_back(p);
        }
    }
    std::vector <vll> pref(26, vll(n+1, 0));
    for (int l=0; l<26; ++l)
        pref[l][1]=1; // winno byc ok z zerem?
    { // wyliczanie dp
        std::priority_queue <prz> mkol,wkol;
        for (int j=2; j<=n; ++j){
            for (int k : mkonv[j-1])
                mkol.push({j-1, k});
            for (int k : wkonv[j-1])
                wkol.push({j-1, k});
            // prep
            while (mkol.size()&&mkol.top().k<j)
                mkol.pop();
            while (wkol.size()&&wkol.top().k<j)
                wkol.pop();
            {// zwiekszanie
                int i=mkol.size() ? mkol.top().p : 0;
                ll p=0;
                for (int l=1; l<26; ++l){
                    DOD(p, MOD-pref[l-1][i]);
                    DOD(p, pref[l-1][j-1]);
                    DOD(pref[l][j], p);
                }
            }
            {// zmniejszanie
                int i=wkol.size() ? wkol.top().p : 0;
                ll p=0;
                for (int l=24; l>=0; --l){
                    DOD(p, MOD-pref[l+1][i]);
                    DOD(p, pref[l+1][j-1]);
                    DOD(pref[l][j], p);
                }
            }
            for (int l=0; l<26; ++l)
                DOD(pref[l][j], pref[l][j-1]);
        }
    }
    ll w=0;
    for (int l=0; l<26; ++l)
        DOD(w, pref[l][n]);
    printf("%lld\n", w);
}

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
misspelling.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~
misspelling.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |             scanf("%d%d", &p, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~

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