Submission #631915

#	Time	Username	Problem	Language	Result	Execution time	Memory
631915		Mahdi	Misspelling (JOI22_misspelling)	C++17	100 / 100	2684 ms	296092 KiB

misspelling

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef pair<int, int> pii;
typedef long long ll;
const int N=5e5+5, M=1e9+7;
int n, m, a[N], b[N], dp[30], s[30], t[30];

int main(){
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int x, y;
        cin>>x>>y;
        if(x<y)
            a[x]=max(a[x], y);
        else
            b[y]=max(x, b[y]);
    }
    priority_queue<pair<pii, int>>mx, mn;
    fill(dp, dp+26, 1);
    for(int i=n-1;i>=1;--i){
        s[0]=0;
        for(int j=1;j<26;++j){
            s[j]=s[j-1]+dp[j-1];
            if(s[j]>=M)
                s[j]-=M;
        }
        t[25]=0;
        for(int j=24;j>=0;--j){
            t[j]=t[j+1]+dp[j+1];
            if(t[j]>=M)
                t[j]-=M;
        }
        for(int j=0;j<26;++j){
            mx.push({{-i, j}, t[j]});
            mn.push({{-i, j}, s[j]});
            s[j]+=t[j];
            if(s[j]>=M)
                s[j]-=M;
            dp[j]+=s[j];
            if(dp[j]>=M)
                dp[j]-=M;
        }
        while(!mx.empty() && -mx.top().F.F<a[i]){
            auto z=mx.top();
            dp[z.F.S]-=z.S;
            if(dp[z.F.S]<0)
                dp[z.F.S]+=M;
            mx.pop();
        }
        while(!mn.empty() && -mn.top().F.F<b[i]){
            auto z=mn.top();
            dp[z.F.S]-=z.S;
            if(dp[z.F.S]<0)
                dp[z.F.S]+=M;
            mn.pop();
        }
    }
    ll ans=0;
    for(int i=0;i<26;++i)
        ans+=dp[i];
    cout<<ans%M<<'\n';
}

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