Submission #956881

#	Time	Username	Problem	Language	Result	Execution time	Memory
956881		hotboy2703	Misspelling (JOI22_misspelling)	C++14	100 / 100	787 ms	389860 KiB

misspelling

//assert,cout,dau // , endl,function chua reference vector,chua pragma log, builtinpopcount,bitset,...

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll MOD = 1e9 + 7;
const ll MAXN = 5e5;
const ll base = 26;
ll cond[MAXN+100][2];
stack <pll> s[base][2];
ll sum[base][2];
ll pre_sum[base][2];
ll sus[base];
ll n,m;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    for (ll i = 1;i <= m;i ++){
        ll u,v;
        cin>>u>>v;
        ll l = min(u,v),r = max(u,v);
        cond[l][u < v] = max(cond[l][u < v],r);
    }
    auto mod = [&](ll &x,ll y) -> void{
//        cout<<x<<' '<<y<<'\n';
        x += y;
        if (x >= MOD)x -= MOD;
        if (x < 0)x += MOD;
    };
    auto mod2 = [&](ll x,ll y) -> ll{
        mod(x,y);
        return x;
    };

    auto add = [&](ll x,ll y,ll id,ll z){
        s[x][y].push(MP(id,z));
        mod(sum[x][y],z);
    };
    auto del = [&](ll x,ll y){
        mod(sum[x][y],-s[x][y].top().se);
        s[x][y].pop();
    };
    for (ll i = 0;i < base;i ++){
        add(i,0,n,1);
    }
//    for (ll j = 0;j < base;j ++){
//            cout<<"CHAR "<<char('a'+ j)<<' ';
//            for (ll k = 0;k < 2;k ++){
//                cout<<sum[j][k]<<' ';
//            }
//            cout<<'\n';
//        }
    for (ll i = n - 1;i >= 1;i --){
        for (ll j = 0;j < base;j ++)sus[j] = mod2(sum[j][0],sum[j][1]);
        for (ll j = base - 1; j >= 0;j --){
            if (j + 1 < base)pre_sum[j][0] = mod2(sus[j+1],pre_sum[j+1][0]);
            else pre_sum[j][0] = 0;
        }
        for (ll j = 0;j < base;j ++){
            if (j)pre_sum[j][1] = mod2(sus[j-1],pre_sum[j-1][1]);
            else pre_sum[j][1] = 0;
//            cout<<j<<' '<<pre_sum[j][1]<<' '<<sus[j-1]<<' '<<pre_sum[j-1][1]<<'\n';
        }
        for (ll j = 0;j < base;j ++){
            for (ll k = 0;k < 2;k ++){
                while (sz(s[j][k]) && s[j][k].top().fi < cond[i][!k])del(j,k);
            }
        }

        for (ll j = 0;j < base;j ++){
            for (ll k = 0;k < 2;k ++){
                if (cond[i][!k] == 0)add(j,k,i,pre_sum[j][k]);
            }
        }
//    for (ll j = 0;j < base;j ++){
//            cout<<"CHAR "<<char('a'+j)<<' ';
//            for (ll k = 0;k < 2;k ++){
//                cout<<sum[j][k]<<' ';
//            }
//            cout<<'\n';
//        }
//    cout<<'\n';

    }
    ll ans = 0;
    for (ll j = 0;j < base;j ++){
            for (ll k = 0;k < 2;k ++){
                mod(ans,sum[j][k]);
            }
        }
    cout<<ans;
}

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