oj.uz

답안 #956877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956877 2024-04-02T15:37:01 Z hotboy2703 Misspelling (JOI22_misspelling) C++14
0 / 100
 344 ms 14932 KB 
//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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 344 ms 14932 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -