Submission #306312

#	Time	Username	Problem	Language	Result	Execution time	Memory
306312		tengiz05	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	138 ms	17012 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct segtree{
	vector<int> t;
	int sz;
	void init(int n){
		sz = 1;
		while(sz < n)sz *= 2;
		t.assign(sz*2, 1);
		for(int i=sz-1; i>0; i--)t[i] = t[i*2] + t[i*2+1];
	}
	void add(int pos, int val){
		pos += sz;
		t[pos] += val;
		for(;pos > 1; pos>>=1)t[pos>>1] = t[pos] + t[pos^1];
	}
	int query(int l, int r){
		if(l > r)return 0;
		l += sz, r += sz;
		int sum = 0;
		for(;l <= r; l>>=1, r>>=1){
			if(l%2 == 1)sum += t[l], l++;
			if(r%2 == 0)sum += t[r], r--;
		}return sum;
	}
};
long long count_swaps(vector<int> a) {
	int n = a.size()/2;
	long long ans = 0;
	
	vector<vector<int>> pos(n+1);
	vector<vector<int>> neg(n+1);
	
	for(int i=0;i<n*2;i++){
		if(a[i] > 0)
			pos[a[i]].push_back(i);
		else 
			neg[abs(a[i])].push_back(i);
	}
	for(int i=1;i<=n;i++){
		sort(pos[i].begin(), pos[i].end());
		sort(neg[i].begin(), neg[i].end());
	}
	vector<pair<int, int>> need;
	for(int i=1;i<=n;i++){
		for(int j=0;j<pos[i].size();j++){
			int r = pos[i][j];
			int l = neg[i][j];
			if(l > r)swap(l, r),ans++;
			need.push_back({l, r});
		}
	}
	sort(need.begin(), need.end());
	segtree seg;
	seg.init(n*2);
	
	for(auto X : need){
		int l = X.first;
		int r = X.second;
		ans += (long long)seg.query(l+1, r-1);
	//	cout << l << ' ' << r << ';' << seg.query(l+1, r-1) << '\n';
		seg.add(l, -1);
		seg.add(r, -1);
	}
	//cout << "; ans = " << ans << '\n';
	return ans;
}

/*

3
-2 -2 -2 2 2 2

3
-2 2 2 -2 -2 2

2 
2 1 -1 -2

*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int j=0;j<pos[i].size();j++){
      |               ~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15