Submission #434549

#	Time	Username	Problem	Language	Result	Execution time	Memory
434549		p_square	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	1 ms	204 KiB

shoes

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

using namespace std;

#define ll long long

int n;

struct node
{
	int octopus, l, r;
	node *lkid, *rkid;

	node(int a, int b){l = a, r = b, octopus = r-l+1;}
	node(){}
};

node *rt;

void build(node *cur)
{
	//cout<<cur->l<<cur->r<<cur->octopus;
	if(cur->l == cur->r)
	{
		cur->octopus = 1;
		return;
	}

	int mid = (cur->l+cur->r)/2;
	cur -> lkid = new node(cur->l, mid);
	cur -> rkid = new node(mid+1, cur->r);
	build(cur->lkid);
	build(cur->rkid);
	return;
}

int query(node *cur, int ql, int qr)
{
	if(cur -> r < ql || cur -> l > qr)
		return 0;
	if(cur -> r <= qr && cur -> l >= ql)
		return cur->octopus;

	return query(cur -> lkid, ql, qr) + query(cur -> rkid, ql, qr);
}

void update(node *cur, int ind)
{
	if(cur->l > ind || cur->r < ind)
		return;

	cur->octopus--;
	if(cur->l == cur->r)
		return;
	update(cur->lkid, ind);
	update(cur->rkid, ind);
}

long long count_swaps(vector<int> s) 
{
	cout<<"Does this give an error?";
	n = s.size()/2;
	vector <int> lef[n], rig[n];
	int beth[2*n];
	for(int i = 0; i<2*n; i++)
	{
		if(s[i]<0)
		{
			lef[-s[i]-1].push_back(i);
		}
		else
		{
			rig[s[i]-1].push_back(i);
		}
	}
	for(int i = 0; i<n; i++)
	{
		for(int j = 0; j<int(lef[i].size()); j++)
		{
			beth[lef[i][j]] = rig[i][j];
			beth[rig[i][j]] = lef[i][j];
		}
	}

	rt = new node(0, 2*n-1);
	build(rt);

	ll cat, Cat = 0;
	for(int i = 0; i<2*n; i++)
	{
		if(beth[i] < i)
			continue;
		update(rt, i);
		update(rt, beth[i]);
		cat = query(rt, i, beth[i]);
		if(s[i]>0)
			cat++;
		Cat+=cat;
	}
	return Cat;
}

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