Submission #814885

#	Time	Username	Problem	Language	Result	Execution time	Memory
814885		groshi	Misspelling (JOI22_misspelling)	C++17	100 / 100	750 ms	160424 KiB

misspelling

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> mniej[600000],wiecej[600000];
int dp[600000][26];
int mod=1e9+7;
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m,x,y;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        if(x<y)
            mniej[x].push_back(y);
        else wiecej[y].push_back(x);
    }
    for(int i=0;i<26;i++)
        dp[1][i]=1;
    priority_queue<pair<int,int> > mnieej,wieecej;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<mniej[i-1].size();j++)
            mnieej.push({i-1,mniej[i-1][j]});
        for(int j=0;j<wiecej[i-1].size();j++)
            wieecej.push({i-1,wiecej[i-1][j]});
        while(mnieej.size() && mnieej.top().second<i)
            mnieej.pop();
        while(wieecej.size() && wieecej.top().second<i)
            wieecej.pop();
        int gosciu=0;
        if(mnieej.size())
            gosciu=mnieej.top().first;
        //cout<<gosciu<<"\n";
        int suma=0;
        for(int j=1;j<26;j++)
        {
            suma-=dp[gosciu][j-1];
            suma+=dp[i-1][j-1];
            suma+=mod;
            suma%=mod;
            dp[i][j]+=suma;
            dp[i][j]+=mod*mod;
            dp[i][j]%=mod;
        }
        /*for(int j=0;j<26;j++)
            cout<<dp[i][j]<<" ";
        cout<<"\n";*/
        if(wieecej.size())
            gosciu=wieecej.top().first;
        else gosciu=0;
        //cout<<gosciu<<"\n";
        suma=0;
        for(int j=24;j>=0;j--)
        {
            suma-=dp[gosciu][j+1];
            suma+=dp[i-1][j+1];
            suma+=mod;
            suma%=mod;
            dp[i][j]+=suma;
            dp[i][j]+=mod*mod;
            dp[i][j]%=mod;
        }
        for(int j=0;j<26;j++)
            dp[i][j]+=dp[i-1][j],dp[i][j]%=mod;
        /*for(int j=0;j<26;j++)
            cout<<dp[i][j]<<" ";
        cout<<"\n";*/
    }
    int wynik=0;
    for(int i=0;i<26;i++)
    {
        wynik+=dp[n][i];
        wynik%=mod;
    }
    cout<<wynik;
    return 0;
}

Compilation message (stderr)

misspelling.cpp: In function 'int32_t main()':
misspelling.cpp:26:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j=0;j<mniej[i-1].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~
misspelling.cpp:28:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int j=0;j<wiecej[i-1].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~~

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