Submission #210796

#TimeUsernameProblemLanguageResultExecution timeMemory
210796dOAObArranging Shoes (IOI19_shoes)C++14
10 / 100
6 ms376 KiB
#include<iostream>
#include<cmath>

#include "shoes.h"
using namespace std;

//#define int long long

#ifdef lioraju
	#define ndbg(x) 
#else
	#define ndbg(x) x
#endif

typedef pair<int, int> pii;

struct FT
{
	int N;
	vector<int> v;
	
	inline int query(int n)
	{
		int sum = 0;
		for (n+=2; n; n-=n&-n)
			sum += v[n];
		return sum;
	}
	
	inline int ask(int a, int b)
	{
		return query(b) - query(a-1);
	}
	
	inline void upd(int n, int vv)
	{
		for (n+=2; n<N; n+=n&-n)
			v[n] += vv;
	}
	
	FT(int cN): N(cN+5), v(N) {  }
};

long long count_swaps(std::vector<int> v)
{
	int n = v.size();
	vector<vector<pii>> sh(n+1);
	for (int i=0;i<n;i++)
		sh[abs(v[i])].push_back({i, v[i]>0});
	
	int sum = 0;
	FT ft(n);
	for (int i=1;i<=n;i++)
	{
		vector<pii> &shi = sh[i];
		int m = shi.size();
		for (int sr=0, j=0;j<m;j++)
		{
			if (!shi[j].second) sum += sr, sr--;
			else sr++;
		}
		
		for (int j=1;j<m;j+=2)
		{
			sum += ft.ask(shi[j-1].first, shi[j].first);
		}
		
		for (int j=0;j<m;j++)
			ft.upd(shi[j].first, 1);
	}
	
	return sum;
}

#ifdef lioraju
	signed main()
	{
		int n; cin>>n, n*=2;
		vector<int> v(n);
		for (int &x: v)
			cin>>x;
		
		cout<<count_swaps(v)<<'\n';
	}
#endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...