Submission #1033911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033911		amirhoseinfar1385	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	328 ms	149080 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int n;
struct fenwick{
	long long fn[maxn];
	void add(int l,int r,int w){
		l++;
		r++;
		r++;
		while(l<maxn){
			fn[l]+=w;
			l+=((-l)&l);
		}
		while(r<maxn){
			fn[r]-=w;
			r+=((-r)&r);
		}
	}
	long long pors(int i){
		i++;
		long long ret=0;
		while(i>0){
			ret+=fn[i];
			i-=((-i)&i);
		}
		return ret;
	}
}fen;
map<int,deque<int>>mp;

long long count_swaps(std::vector<int> s) {
	n=s.size();
	long long mainres=0;
	for(int i=0;i<n;i++){
		if(mp[-s[i]].size()==0){
			mp[s[i]].push_back(i);
			continue;
		}
		auto x=mp[-s[i]].front();
		mp[-s[i]].pop_front();
		mainres+=(i-x-1)-fen.pors(x);
		mainres+=(s[i]<0);
		fen.add(x,i,1);
	}
	return mainres;
}

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