Submission #1516825

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
int abs(int x){
if(x<0)
    return x*-1;
else
    return x;
}
int main(){
int n;
cin>>n;
int i,j;
pair<int,int> a[n+1];
for(i=1;i<=n;i++){
    int g;
    cin>>g;
    a[i]=mp(g,i);

}
sort(a+1,a+n+1);
set<int> a0;
set<int> a1;
set<int> b0;
set<int> b1;
int c[n+1];
for(i=n;i>=1;i--){

   int x=abs(i-a[i].second);

   c[a[i].second]=x%2;
if(a[i].second%2){

    if(x%2)
        a1.insert(a[i].second);
    else
        a0.insert(a[i].second);

}
else{



    if(x%2)
        b1.insert(a[i].second);
    else
        b0.insert(a[i].second);





}}

int ans=0;
set<int>::iterator s;
for(i=n;i>=1;i--){

     if(c[a[i].second]==0)
        {
            if(a[i].second%2)
                a0.erase(a[i].second);
            else
            b0.erase(a[i].second);
            continue;}
     ans++;

     if(a[i].second%2){

        a1.erase(a[i].second);
        if(b1.empty()){
            s=b0.begin();
            c[*s]=1;
            b0.erase(*s);
            b1.insert(*s);

        }
        else{
           s=b1.begin();
           c[*s]=0;
           b1.erase(*s);
           b0.insert(*s);


        }

     }
     else{

        b1.erase(a[i].second);
        if(a1.empty()){
            s=a0.begin();
            c[*s]=1;
            a0.erase(*s);
            a1.insert(*s);

        }
        else{
           s=a1.begin();
           c[*s]=0;
           a1.erase(*s);
           a0.insert(*s);


        }

     }







}
cout<<ans<<endl;



return 0;
}

Submission Info

Judge Result