Submission #1368344

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <map>
#include <string>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <algorithm> 
#include <ctime>

#define MaxN 100005
#define INF 2140000000
 
using namespace std;

FILE *IN,*OUT;

int v[MaxN],a[MaxN],N,ans=0;
int Search(int val)
{
	int lw=1,hi=N,mid;
	while(lw<=hi)
	{
		int mid=(lw+hi)>>1;
		if(v[mid]>val)
			hi=mid-1;
		else if(v[mid]<val)
			lw=mid+1;
		else return mid;
	}
}
int main()
{
	cin>>N;
	for(int i=1;i<=N;i++)
	{
		cin>>a[i];
		v[i]=a[i];
	}
	sort(v+1,v+1+N);
	for(int i=1;i<=N;i++)
	{
		if((i%2)^Search(a[i]))
			ans++;
	}
	cout<<ans/2;
	return 0;
}

Submission Info

Judge Result