#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>dp,mergy;
vector<int>all;
int n;
int calmina(int a,int b,int pi,int pii){
int wi=upper_bound(mergy[pi].begin(),mergy[pi].end(),min(a,b))-mergy[pi].begin();
int wii=upper_bound(mergy[pii].begin(),mergy[pii].end(),min(a,b))-mergy[pii].begin();
if(dp[pi][wi]<dp[pii][wii]){
if(b==min(a,b)){
return dp[pi][wi];
}
else{
int z=upper_bound(mergy[pii].begin(),mergy[pii].end(),b)-mergy[pii].begin();
return dp[pii][z];
}
}
else{
if(b==min(a,b)){
return dp[pii][wii];
}
else{
int z=upper_bound(mergy[pi].begin(),mergy[pi].end(),b)-mergy[pi].begin();
return dp[pi][z];
}
}
}
vector<int>merge(vector<int>a,vector<int>b){
int i=0,j=0;
vector<int>ret;
while(i<(int)a.size()&&j<(int)b.size()){
if(a[i]<b[j]){
ret.push_back(a[i]);
i++;
}
else{
ret.push_back(b[j]);
j++;
}
}
while(i<(int)a.size()){
ret.push_back(a[i]);
i++;
}
while(j<(int)b.size()){
ret.push_back(b[j]);
j++;
}
return ret;
}
void solve(int u){
if(u==0){
return ;
}
if(u*2>=n+1){
dp[u]={u,u};
mergy[u].push_back(u);
return solve(u-1);
}
if(u*2==n)
{
mergy[u]=merge(mergy[(u<<1)],{u});
dp[u].resize((int)mergy[u].size()+1);
for(int j=0;j<(int)dp[u].size();j++){
if(j==(int)dp[u].size()-1){
dp[u][j]=dp[u*2][j-1];
}
else{
if(mergy[u][j]<all[u*2]){
dp[u][j]=u;
continue;
}
int p=upper_bound(mergy[u*2].begin(),dp[u*2].end(),mergy[u][j])-mergy[u*2].begin();
dp[u][j]=dp[u*2][p];
}
}
return solve(u-1);
}
mergy[u]=merge(mergy[(u<<1)],{u});
mergy[u]=merge(mergy[u],mergy[(u<<1)^1]);
dp[u].resize((int)mergy[u].size()+1);
for(int j=0;j<(int)dp[u].size();j++){
if(j==(int)dp[u].size()-1){
dp[u][j]=calmina(max(all[u*2+1],all[u*2]),mergy[u].back()+2,u*2,u*2+1);
}
else{
if(mergy[u][j]-1<all[u*2]&&mergy[u][j]-1<all[u*2+1]){
dp[u][j]=u;
continue;
}
if(all[u*2]<mergy[u][j]-1&&all[u*2]<all[u*2+1]){
dp[u][j]=u*2;
continue;
}
dp[u][j]=calmina(max(all[u*2],all[u*2+1]),mergy[u][j]-1,u*2,u*2+1);
}
}
return solve(u-1);
}
vector<int>res;
void calres(int u){
if(u>n){
return ;
}
if(u*2>n){
return calres(u+1);
}
if(u*2==n){
if(all[u]<all[u*2]){
return calres(u+1);
}
else{
swap(all[u],all[u*2]);
return calres(u+1);
}
}
int p=upper_bound(mergy[u].begin(),mergy[u].end(),all[u])-mergy[u].begin();
if(dp[u][p]==u){
return calres(u+1);
}
if(all[u*2]<all[u*2+1]&&all[u*2]<all[u]){
swap(all[u*2],all[u]);
return calres(u+1);
}
int z=lower_bound(mergy[u*2].begin(),mergy[u*2].end(),dp[u][p])-mergy[u*2].begin();
if(z!=(int)mergy[u*2].size()&&mergy[u*2][z]==dp[u][p]){
swap(all[u],all[u*2]);
if(all[u]>all[u*2+1]){
swap(all[u],all[u*2+1]);
}
return calres(u+1);
}
swap(all[u],all[u*2+1]);
return calres(u+1);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
res.resize(n+1);
all.resize(n+1);
mergy.resize(n+1);
dp.resize(n+1);
for(int i=1;i<=n;i++){
cin>>all[i];
}
solve(n);
/*for(int i=1;i<=n;i++){
for(auto x:dp[i]){
cout<<x<<" ";
}
cout<<"\n";
}
cout<<"\n";*/
calres(1);
for(int i=1;i<=n;i++){
cout<<all[i]<<" ";
}
cout<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
