Submission #893059

#	Time	Username	Problem	Language	Result	Execution time	Memory
893059		Hugo1729	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	232 ms	275692 KiB

shoes

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

using namespace std;

struct SegTree{
	vector<int> e;
	int size;

	SegTree(int n){
		size=1;
		while(size<n) size<<=1;
		e=vector<int>(2*size,0);};

	void update(int v, int l, int r, int x, int y){
		if (r<x||y<l) return;
		if (x<=l&&r<=y){ e[v]++; return;}

		int m=(l+r)/2;

		update(2*v,l,m,x,y);
		update(v*2+1,m+1,r,x,y);
	}

	int query(int v){
		int ans=0;
		v+=size-1;

		while(v>0){
			ans += e[v];
			v/=2;
		}
		return ans;
	}
};


long long count_swaps(std::vector<int> s) {
	int n= s.size();
	long long ans =0;

	SegTree seg(n);

	deque<int> shoes[n+1][2];

	for(int i=0;i<n;i++){
		int shoe=s[i];
		int j=(int)(shoe>0);
		shoe = abs(shoe);

		shoes[shoe][j].push_back(i+1);
	}

	for(int i=0;i<n;i++){
		int shoe=s[i];
		int j=(int)(shoe>0);
		shoe = abs(shoe);

		if (shoes[shoe][j].front() == i+1){
			int pos = shoes[shoe][1-j].front();
			shoes[shoe][1-j].pop_front();
			shoes[shoe][j].pop_front();

			ans+=(pos+seg.query(pos))-(i+1+seg.query(i+1))-1;
			ans+=j;

			seg.update(1,1,seg.size,i+1,pos);
		}
	}

	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