Submission #569062

#	Time	Username	Problem	Language	Result	Execution time	Memory
569062		dantoh000	Misspelling (JOI22_misspelling)	C++14	100 / 100	1200 ms	116480 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
int n,m;
int up[500005];
int down[500005];
int dp[500005][30];
set<int> gup, gdown;
int tot[500005];
int mod = 1000000007;

int main(){
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++){
        up[i] = down[i] = i;
    }
    for (int i = 0,a,b; i < m; i++){
        scanf("%d%d",&a,&b);
        if (a < b) up[a] = max(up[a], b);
        else down[b] = max(down[b], a);
    }
    for (int i = 1; i <= n+1; i++){
        gup.insert(i);
        gdown.insert(i);
    }
    for (int i = 0; i < 26; i++) tot[i] = 1;
    for (int i = n; i >= 1; i--){
        while (*gup.lower_bound(i+1) <= up[i]){
            int tmp = *gup.lower_bound(i+1);
            gup.erase(tmp);
            ///printf("%d cannot transition to %d up\n");
            int pfx = 0;
            for (int j = 25; j >= 0; j--){
                tot[j] = (tot[j] - pfx + mod)%mod;
                pfx = (pfx + dp[tmp][j])%mod;
            }
        }
        while (*gdown.lower_bound(i+1) <= down[i]){
            int tmp = *gdown.lower_bound(i+1);
            gdown.erase(tmp);
            ///printf("%d cannot transition to %d down\n");
            int pfx = 0;
            for (int j = 0; j < 26; j++){
                tot[j] = (tot[j] - pfx + mod)%mod;
                pfx = (pfx + dp[tmp][j])%mod;
            }
        }
        int sum = 0;
        for (int j = 0; j < 26; j++){

            dp[i][j] = tot[j];
            //printf("%d ",dp[i][j]);
            sum = (sum+dp[i][j])%mod;
        }
        //printf("\n");
        for (int j = 0; j < 26; j++){
            tot[j] = ((tot[j] + sum)%mod - dp[i][j] + mod)%mod;
        }
    }
    int ans = 0;
    for (int i = 0; i < 26; i++){
        ans = (ans + dp[1][i])%mod;
    }
    printf("%d\n",ans);




}

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:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

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