Submission #877801

#	Time	Username	Problem	Language	Result	Execution time	Memory
877801		mahmoudbadawy	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	235 ms	15020 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

const int N=2e5+5;

int btree[4*N];

void build(int node,int l,int r)
{
	if(l==r)
	{
		btree[node]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(node<<1,l,mid);
	build((node<<1)|1,mid+1,r);
	btree[node]=btree[node<<1]+btree[(node<<1)|1];
}

void update(int node,int l,int r,int ind)
{
	if(r<ind||ind<l) return;
	if(l==r)
	{
		btree[node]=0;
		return;
	}
	int mid=(l+r)>>1;
	update(node<<1,l,mid,ind);
	update((node<<1)|1,mid+1,r,ind);
	btree[node]=btree[node<<1]+btree[(node<<1)|1];
}

int query(int node,int l,int r,int ql,int qr)
{
	if(r<ql||qr<l) return 0;
	if(ql<=l&&r<=qr) return btree[node];
	int mid=(l+r)>>1;
	return query(node<<1,l,mid,ql,qr)+query((node<<1)|1,mid+1,r,ql,qr);
}

long long count_swaps(std::vector<int> s) {
	set<pair<int,int> > ss;
	int n=s.size();
	for(int i=0;i<n;i++)
	{
		ss.insert({s[i],i});
	}
	build(1,0,n-1);
	long long ans=0;
	for(int i=0;i<n;i++)
	{
		if(ss.find({s[i],i})==ss.end()) continue;
		auto ot=*ss.lower_bound({-s[i],i});
		ans+=query(1,0,n-1,i+1,ot.second-1);
		ans+=s[i]>0;
		update(1,0,n-1,i);
		update(1,0,n-1,ot.second);
		ss.erase(ot);
	}
	return ans;
}

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