제출 #544569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544569		Rafi22	Misspelling (JOI22_misspelling)	C++14	100 / 100	1254 ms	193636 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=500007;

ll DP[N][26];
ll cnt[26];
vector<int>poc1[N],kon1[N];
vector<int>poc2[N],kon2[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,a,b;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        if(a<b)
        {
            poc1[a].pb(a);
            kon1[b].pb(a);
        }
        else
        {
            poc2[b].pb(b);
            kon2[a].pb(b);
        }
    }
    for(int i=0;i<26;i++) DP[1][i]=1;
    multiset<int>Q1,Q2;
    for(auto x:poc1[1]) Q1.insert(x);
    for(auto x:poc2[1]) Q2.insert(x);
    for(int i=2;i<=n;i++)
    {
        int x=0,y=0;
        if(sz(Q1)>0) x=*--Q1.end();
        if(sz(Q2)>0) y=*--Q2.end();
        memset(cnt,0,sizeof cnt);
        //mniejszy
        ll act=0;
        for(int j=25;j>=0;j--)
        {
            cnt[j]=act;
            act=(act+DP[i-1][j]-DP[y][j]+mod)%mod;
        }
        //wiekszy
        act=0;
        for(int j=0;j<26;j++)
        {
            cnt[j]=(cnt[j]+act)%mod;
            act=(act+DP[i-1][j]-DP[x][j]+mod)%mod;
        }
        for(int j=0;j<26;j++) DP[i][j]=(DP[i-1][j]+cnt[j])%mod;
        for(auto x:kon1[i]) Q1.erase(Q1.find(x));
        for(auto x:kon2[i]) Q2.erase(Q2.find(x));
        for(auto x:poc1[i]) Q1.insert(x);
        for(auto x:poc2[i]) Q2.insert(x);
    }
    ll ans=0;
    for(int i=0;i<26;i++) ans=(ans+DP[n][i])%mod;
    cout<<ans;

    return 0;
}

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