제출 #147406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
147406		mosiashvililuka	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	803 ms	149240 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,f[200009],fen[200009],pas;
long long read(long long q){
	long long jm=0;
	while(q>=1){
		jm+=fen[q];
		q=q-(q&(-q));
	}
	return jm;
}
void upd(long long q, long long w){
	while(q<=a){
		fen[q]+=w;
		q=q+(q&(-q));
	}
}
bool bo[200009];
map <long long, deque <long long> > dez;
long long count_swaps(vector <int> S){
a=S.size();
	for(b=1; b<=a; b++) f[b]=S[b-1];
	for(b=1; b<=a; b++){
		dez[f[b]].push_back(b);
	}
	for(b=1; b<=a; b++) upd(b,1);
	for(b=1; b<=a; b++){
		if(f[b]<0){
			if(dez[f[b]][0]!=b) continue;
			dez[f[b]].pop_front();
			pas+=read(dez[-f[b]][0])-2;
			upd(b,-1);
			upd(dez[-f[b]][0],-1);
			dez[-f[b]].pop_front();
		}else{
			if(dez[f[b]][0]!=b) continue;
			dez[f[b]].pop_front();
			pas+=read(dez[-f[b]][0])-1;
			upd(b,-1);
			upd(dez[-f[b]][0],-1);
			dez[-f[b]].pop_front();
		}
	}
	return pas;
}

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