Submission #589416

#	Time	Username	Problem	Language	Result	Execution time	Memory
589416		qwerasdfzxcl	Misspelling (JOI22_misspelling)	C++14	100 / 100	407 ms	153700 KiB

misspelling

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int MOD = 1e9+7;
ll dp[500500][26];
int pos[2][500500]; ///up -> 0, down -> 1
vector<int> E[2][500500];

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i=1;i<=m;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        if (x<y) E[0][x].push_back(y);
        else E[1][y].push_back(x);
    }

    for (int k=0;k<2;k++){
        priority_queue<pair<int, int>> pq;
        for (int i=1;i<=n;i++){
            while(!pq.empty() && pq.top().second<i) pq.pop();
            if (!pq.empty()) pos[k][i] = pq.top().first;

            for (auto &r:E[k][i]) pq.emplace(i, r);
        }
    }


    fill(dp[1], dp[1]+26, 1);
    for (int i=2;i<=n;i++){
        for (int k=0;k<26;k++) dp[i][k] = dp[i-1][k];

        ll cur = 0;
        for (int k=1;k<26;k++){
            cur += dp[i-1][k-1] - dp[pos[0][i]][k-1] + MOD;
            while(cur>=MOD) cur -= MOD;

            dp[i][k] += cur;
            if (dp[i][k]>=MOD) dp[i][k] -= MOD;
        }

        cur = 0;
        for (int k=24;k>=0;k--){
            cur += dp[i-1][k+1] - dp[pos[1][i]][k+1] + MOD;
            while(cur>=MOD) cur -= MOD;

            dp[i][k] += cur;
            if (dp[i][k]>=MOD) dp[i][k] -= MOD;
        }
    }

    ll ans = 0;
    for (int k=0;k<26;k++) ans = (ans + dp[n][k]) % MOD;
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

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

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