Submission #1,293

2022-03-30 16:05:09

cpp14

Accepted 100/100

120ms

38180 KiB

#include <bits/stdc++.h>
using namespace std;

int n;
string s;
int suf[1000006];
int ans[1000006];
int best[1000006];
stack<int> st;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>s;

    for(int i=n-1;i>=0;i--){
        if(s[i]=='H'){
            best[i]=i;
            st.push(i);
        }
        else{
            if(!st.empty()) st.pop();
            best[i]=st.empty()?n:st.top();
        }
    }

    int h=0,m=0,mh=0;
    for(int i=n-1;i>=0;i--){
        suf[i]=suf[i+1];
        if(s[i]=='H') ++h;
        else if(s[i]=='K'){
            if(h){
                --h; suf[i]++;
            }
            else if(mh){
                ++m; --mh;
            }
            else if(m){
                --m; suf[i]++;
            }
        }
        else{
            if(h){
                --h; ++mh;
                suf[i]++;
            }
            else{
                ++m;
            }
        }
        ans[i]=suf[i]+m/2;
    }

    for(int i=0;i<n;i++){
        if(best[i] != n){
            cout << (best[i]-i)/2 << ' ';
        }

        else{
            cout << ans[i] << ' ';
        }
    }
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	2ms	1832 KiB
		2	Accepted	2ms	1980 KiB
subtask2	7/7
		3	Accepted	1ms	1880 KiB
		4	Accepted	1ms	1908 KiB
subtask3	9/9
		5	Accepted	2ms	2092 KiB
		6	Accepted	2ms	2012 KiB
		7	Accepted	2ms	2012 KiB
subtask4	14/14
		8	Accepted	101ms	28540 KiB
		9	Accepted	108ms	29584 KiB
		10	Accepted	104ms	30564 KiB
		11	Accepted	108ms	31532 KiB
		12	Accepted	97ms	31448 KiB
		13	Accepted	97ms	32412 KiB
		14	Accepted	104ms	32296 KiB
		15	Accepted	101ms	32752 KiB
subtask5	11/11
		16	Accepted	1ms	7116 KiB
		17	Accepted	1ms	7124 KiB
		18	Accepted	1ms	7124 KiB
subtask6	29/29
		19	Accepted	2ms	7316 KiB
		20	Accepted	2ms	7324 KiB
		21	Accepted	2ms	7328 KiB
		22	Accepted	1ms	7336 KiB
subtask7	30/30
		23	Accepted	120ms	33772 KiB
		24	Accepted	119ms	33172 KiB
		25	Accepted	114ms	33560 KiB
		26	Accepted	114ms	33188 KiB
		27	Accepted	119ms	33016 KiB
		28	Accepted	119ms	33720 KiB
		29	Accepted	109ms	34696 KiB
		30	Accepted	114ms	34612 KiB
		31	Accepted	115ms	34884 KiB
		32	Accepted	116ms	33416 KiB
		33	Accepted	104ms	34400 KiB
		34	Accepted	108ms	33912 KiB
		35	Accepted	104ms	34008 KiB
		36	Accepted	103ms	34268 KiB
		37	Accepted	98ms	35232 KiB
		38	Accepted	101ms	36220 KiB
		39	Accepted	107ms	37208 KiB
		40	Accepted	108ms	38180 KiB