/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 2ms 532.0 KiB
#3 Accepted 3ms 532.0 KiB
#4 Accepted 4ms 344.0 KiB
#5 Accepted 15ms 1.41 MiB
#6 Accepted 10ms 1.41 MiB
#7 Accepted 11ms 1.41 MiB
#8 Accepted 15ms 1.457 MiB
#9 Accepted 14ms 1.41 MiB
#10 Accepted 10ms 1.473 MiB
#11 Accepted 1ms 532.0 KiB
#12 Accepted 1ms 532.0 KiB
#13 Accepted 1ms 336.0 KiB
#14 Accepted 1ms 536.0 KiB
#15 Accepted 1ms 532.0 KiB
#16 Accepted 1ms 532.0 KiB
#17 Accepted 1ms 532.0 KiB
#18 Accepted 1ms 532.0 KiB
#19 Accepted 1ms 360.0 KiB
#20 Accepted 1ms 536.0 KiB
#21 Accepted 1ms 532.0 KiB
#22 Accepted 1ms 532.0 KiB
#23 Accepted 1ms 448.0 KiB
#24 Accepted 1ms 444.0 KiB
#25 Accepted 1ms 368.0 KiB
#26 Accepted 1ms 304.0 KiB
#27 Accepted 1ms 532.0 KiB
#28 Accepted 1ms 532.0 KiB
#29 Accepted 1ms 512.0 KiB
#30 Accepted 1ms 508.0 KiB
#31 Accepted 1ms 316.0 KiB
#32 Accepted 1ms 344.0 KiB
#33 Accepted 1ms 532.0 KiB
#34 Accepted 1ms 348.0 KiB
#35 Accepted 4ms 340.0 KiB
#36 Accepted 4ms 532.0 KiB
#37 Accepted 4ms 536.0 KiB
#38 Accepted 4ms 532.0 KiB
#39 Accepted 3ms 532.0 KiB
#40 Accepted 3ms 504.0 KiB
#41 Accepted 3ms 324.0 KiB
#42 Accepted 3ms 452.0 KiB
#43 Accepted 3ms 500.0 KiB
#44 Accepted 3ms 532.0 KiB
#45 Accepted 3ms 492.0 KiB
#46 Accepted 2ms 536.0 KiB
#47 Accepted 1ms 532.0 KiB
#48 Accepted 1ms 324.0 KiB
#49 Accepted 1ms 424.0 KiB
#50 Accepted 1ms 536.0 KiB
#51 Accepted 1ms 532.0 KiB
#52 Accepted 1ms 348.0 KiB
#53 Accepted 1ms 372.0 KiB
#54 Accepted 1ms 320.0 KiB
#55 Accepted 1ms 532.0 KiB
#56 Accepted 1ms 532.0 KiB
#57 Accepted 1ms 532.0 KiB
#58 Accepted 1ms 324.0 KiB
#59 Accepted 1ms 532.0 KiB
#60 Accepted 1ms 488.0 KiB
#61 Accepted 1ms 532.0 KiB
#62 Accepted 1ms 532.0 KiB
#63 Accepted 1ms 320.0 KiB
#64 Accepted 1ms 764.0 KiB
#65 Accepted 1ms 576.0 KiB
#66 Accepted 1ms 532.0 KiB
#67 Accepted 1ms 532.0 KiB
#68 Accepted 1ms 532.0 KiB
#69 Accepted 1ms 448.0 KiB
#70 Accepted 1ms 532.0 KiB
#71 Accepted 1ms 484.0 KiB
#72 Accepted 1ms 532.0 KiB
#73 Accepted 1ms 504.0 KiB
#74 Accepted 1ms 532.0 KiB
#75 Accepted 1ms 340.0 KiB
#76 Accepted 1ms 320.0 KiB
#77 Accepted 1ms 524.0 KiB
#78 Accepted 1ms 532.0 KiB
#79 Accepted 1ms 532.0 KiB
#80 Accepted 1ms 496.0 KiB
#81 Accepted 1ms 532.0 KiB
#82 Accepted 1ms 396.0 KiB
#83 Accepted 1ms 344.0 KiB
#84 Accepted 1ms 396.0 KiB
#85 Accepted 1ms 532.0 KiB
#86 Accepted 1ms 532.0 KiB
#87 Accepted 1ms 532.0 KiB
#88 Accepted 1ms 532.0 KiB
#89 Accepted 1ms 336.0 KiB
#90 Accepted 1ms 348.0 KiB
#91 Accepted 1ms 412.0 KiB
#92 Accepted 1ms 532.0 KiB
#93 Accepted 1ms 532.0 KiB
#94 Accepted 1ms 532.0 KiB
#95 Accepted 1ms 532.0 KiB
#96 Accepted 1ms 508.0 KiB
#97 Accepted 1ms 528.0 KiB
#98 Accepted 1ms 532.0 KiB
#99 Accepted 1ms 480.0 KiB
#100 Accepted 1ms 532.0 KiB

Code

/*
 *   Copyright (c) 2025 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
char sg[800005];
void build(int node,int start,int end,string &s)
{
    if(start == end)
    {
        sg[node] = s[start];
        return;
    }
    int mid = (start + end)/2;
    build(node*2,start,mid,s);
    build(node*2+1,mid+1,end,s);
    sg[node] = min(sg[node*2] , sg[node*2+1]);
}

char query(int node,int start,int end,int l,int r)
{
    if(l>end || r<start) return ('z'+1);
    if(l<=start && r>=end) return sg[node];
    int mid = (start + end)/2;
    return min(query(node*2,start,mid,l,r) , query(node*2+1,mid+1,end,l,r));
}

int main()
{
    // string outp = "output"+to_string(tc)+".txt";
    // string inp = "input"+to_string(tc)+".txt";
    // ofstream file(outp);
    // freopen(inp.c_str(),"r",stdin);

    int n,k; cin >> n >> k;
    string s; cin >> s;
    build(1,0,n-1,s);

    for(int i=0;i+k<=n;i++)
    {
        char mn = query(1,0,n-1,i,i+k-1);
        if(mn < s[i] || i+k==n) sort(s.begin()+i,s.begin()+i+k) , i+=(k-1);
    }
    cout<<s<<endl;
}

// int main()
// {
//     for(int i=0;i<100;i++) main2(i);
// }

Information

Submit By
Type
Submission
Problem
P1230 Lexicographically Smallest Rearrangement
Language
C++17 (G++ 13.2.0)
Submit At
2025-08-30 15:56:18
Judged At
2025-08-30 15:56:18
Judged By
Score
100
Total Time
15ms
Peak Memory
1.473 MiB