Submission #1185785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185785		nikaa123	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	258 ms	148896 KiB

shoes

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

const int N = 2e5+5;

long long  t[4*N];
long long fix[N];
map<int,queue<int>> v;

void update(int node, int tl, int tr,int pos) {
	if (tl == tr) {
		t[node]++;
		return;
	}
	int mid = (tl+tr)/2;
	if (pos <= mid) {
		update(node*2,tl,mid,pos);
	} else {
		update(node*2+1,mid+1,tr,pos);
	}
	t[node] = t[node*2]+t[node*2+1];
}

long long getsum(int node, int tl, int tr, int l, int r) {
	if (l > r) return 0;
	if (tl == l && tr == r) {
		return t[node];
	}
	int mid = (tl+tr)/2;
	return (getsum(node*2,tl,mid,l,min(r,mid))+getsum(node*2+1,mid+1,tr,max(mid+1,l),r));
}

long long count_swaps(std::vector<int> s) {
	long long n = s.size();
	s.insert(s.begin(),0);
	for (int i = 1; i <= n; i++) {
		v[s[i]].pb(i);
	}
	long long op = 0;
	for (int i = 1; i <= n; i++) {
		if (fix[i]) continue;
		long long a = s[i];
		long long b = -s[i];
		int ib = v[b].front();
		v[b].pop();	
		op += (ib-i-1-getsum(1,1,n,i,ib));
		update(1,1,n,ib);
		if (a>=0) op++;
		fix[ib]++;
	}
	return op;
}

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