제출 #967378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
967378		lsi	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	16 ms	21688 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int nm[200100];
bool taken[200100];
int pir[200100];
vector<int> l[200100],r[200100];
int tre[200100];

int lowbit(int i){
	return i&(-i);
}

int ct(int p){
	int tp=0;
	for (int i=p;i;i-=lowbit(i)){
		tp+=tre[i];
	}
	return tp;
}

void ad(int p){
	for (int i=p;i<=200100;i+=lowbit(i)){
		tre[i]++;
	}
}

long long count_swaps(vector<int> s) {
	ll ans=0;
	memset(taken,false,sizeof taken);
	int n=s.size();
	for (int i=1;i<=n*2;i++){
		nm[i]=s[i-1];
		int tp=nm[i];
		if (tp<0) tp*=-1;
		if (nm[i]<0){
			if (!r[tp].empty()){
				pir[i]=r[tp][0];
				pir[r[tp][0]]=i;
				r[tp].erase(r[tp].begin());
				continue;
			}
			l[tp].push_back(i);
		}else{
			if (!l[tp].empty()){
				pir[i]=l[tp][0];
				pir[l[tp][0]]=i;
				l[tp].erase(l[tp].begin());
				continue;
			}
			r[tp].push_back(i);
		}
	}
	for (int i=1;i<=n*2;i++){
		if (taken[i]) continue;
		int tp,tpa=0;
		if (nm[i]>0){
			tpa+=1;
		}
		tp=pir[i];
		tpa+=tp-i-1;
		tpa-=ct(tp-1)-ct(i);
		taken[tp]=true;
		ad(tp);
		ans+=tpa;
		//printf("%d %d\n",tp,tpa);
	}
	return ans;
}

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