oj.uz

Submission #210796

# Submission time Handle Problem Language Result Execution time Memory
210796 2020-03-18T11:11:55 Z dOAOb Arranging Shoes (IOI19_shoes) C++14
10 / 100
 6 ms 376 KB 
#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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Incorrect 5 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Incorrect 6 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Incorrect 5 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Incorrect 5 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Incorrect 5 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -