제출 #956877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
956877		hotboy2703	Misspelling (JOI22_misspelling)	C++14	0 / 100	344 ms	14932 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 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 add = [&](ll x,ll y,ll id,ll z){
        s[x][y].push(MP(id,z));
        sum[x][y]+=z;
    };
    auto del = [&](ll x,ll y){
        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] = sum[j][0] + sum[j][1];
        for (ll j = base - 1; j >= 0;j --){
            if (j + 1 < base)pre_sum[j][0] = 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] = 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 ++){
                ans += sum[j][k];
            }
        }
    cout<<ans;
}

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