Submission #1268639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268639		jump	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	179 ms	25684 KiB

shoes

#include <bits/stdc++.h>
std::map<long long,std::vector<long long>> lp;
long long fwk[300000];
bool mark[300000];
long long upd(long long idx,long long n){
	while(idx<300000){
		fwk[idx]+=n;
		idx += ((idx) & (-idx));
		//std::cout << idx;
	}
	return 1;
}
long long look(long long idx){
	long long sum = 0;
	while(idx>0){
		sum+=fwk[idx];
		idx -= idx & -idx;
	}
	return sum;
}
long long count_swaps(std::vector<int> s){
	for(long long i=1;i<=200010;i++){
		upd(i,1);
	}
	//std::cout << 123;
	for(long long i=s.size()-1;i>=0;i--){
		auto num = s[i];
		if(lp.find(num)==lp.end()){
			lp[num]={i+1};
		}
		else{
			lp[num].push_back(i+1);
		}
	}
	long long sum = 0;
	for(long long i=0;i<s.size();i++){
		
		if(!mark[i+1]){
			mark[i+1]=true;
		}else continue;
		upd(i+1,-1);
		long long match = lp[-s[i]].back();lp[-s[i]].pop_back();
		lp[s[i]].pop_back();
		sum+=look(match)-1;
		//std::cout << i+1 << ' ' << match << ' ' << look(match) << '\n';
		upd(match,-1);
		mark[match]=true;
		if(s[i]>0)sum+=1;
	}
	return sum;
}

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