#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
int n,pa[200001],height[200001];
char mun[200001],maxc[200001];
bool check[200001];
using namespace std;
vector<int> list[200001];
int parent(int a){
if(pa[a]==-1)
return a;
return parent(pa[a]);
}
void back(int s,int e){
if(s+1==e)
return ;
if((e-s)%2==0){
back(s,(s+e)/2);
back((s+e)/2,e);
}
else{
back(s,(s+e)/2);
back((s+e)/2+1,e);
}
e--;
int pa1,pa2;
while(s<=e){
pa1=parent(s);
pa2=parent(e);
if(pa1!=pa2){
if(height[pa1]==height[pa2])
height[pa1]++;
if(height[pa1]>height[pa2]){
pa[pa2]=pa1;
if(maxc[pa2]>maxc[pa1])
maxc[pa1]=maxc[pa2];
}
else{
pa[pa1]=pa2;
if(maxc[pa1]>maxc[pa2])
maxc[pa2]=maxc[pa1];
}
}
s++;
e--;
}
}
int main(){
scanf("%s",mun);
int i,j;
n=strlen(mun);
for(i=0;i<n;i++){
pa[i]=-1;
maxc[i]=mun[i];
}
back(0,n);
int par;
for(i=0;i<n;i++){
par=parent(i);
list[par].push_back(i);
}
for(i=0;i<n;i++){
par=parent(i);
if(check[par]) continue;
check[par]=1;
if(mun[i]==maxc[par]){
for(j=0;j<list[par].size();j++)
mun[list[par][j]]=maxc[par];
}
else{
maxc[par]=mun[i]+1;
for(j=0;j<list[par].size();j++)
mun[list[par][j]]=maxc[par];
for(j=i;j<n;j++){
par=parent(j);
if(check[par]) continue;
mun[j]='a';
}
break;
}
}
printf("%s\n",mun);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
8428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
