Submission #198298

#	Time	Username	Problem	Language	Result	Execution time	Memory
198298		Akashi	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	229 ms	31648 KiB

shoes

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

struct grup{
	int x, y;
	bool operator < (const grup &aux)const{
		if((x + y) / 2 != (aux.x + aux.y) / 2) return (x + y) / 2 < (aux.x + aux.y) / 2;
		return x < aux.x;
	}
};

grup a[100005];

set <int> lf[200005], rf[200005];
int n;

int Arb[800005], Lazy[800005];

void propag(int nod){
	for(int i = nod * 2; i <= nod * 2 + 1 ; ++i){
		Lazy[i] += Lazy[nod];
		Arb[i] += Lazy[nod]; 
	}
	Lazy[nod] = 0;
}

void build(int st = 1, int dr = n, int nod = 1){
	Lazy[nod] = 0;
	if(st == dr){
		Arb[nod] = st;
		return ;
	}
	
	int mij = (st + dr) / 2;
	build(st, mij, nod * 2);
	build(mij + 1, dr, nod * 2 + 1);
}

void update(int x, int y, int val, int st = 1, int dr = n, int nod = 1){
	if(x <= st && dr <= y){
		Lazy[nod] += val;
		Arb[nod] += val;
		return ;
	}
	
	propag(nod);
	
	int mij = (st + dr) / 2;
	if(x <= mij) update(x, y, val, st, mij, nod * 2);
	if(mij + 1 <= y) update(x, y, val, mij + 1, dr, nod * 2 + 1);
}

int query(int x, int st = 1, int dr = n, int nod = 1){
	if(st == dr) return Arb[nod];
	propag(nod);
	
	int mij = (st + dr) / 2;
	if(x <= mij) return query(x, st, mij, nod * 2);
	else return query(x, mij + 1, dr, nod * 2 + 1);
}

long long count_swaps(vector<int> s) {
	int NR = 0;
	n = s.size();
	long long Sol = 0;
	for(int i = 1; i <= n ; ++i){
		int x = s[i - 1];
		if(x < 0){
			x = -x;
			if(!rf[x].empty()){
				a[++NR] = {i, *rf[x].begin()};
				rf[x].erase(rf[x].begin());
				//++Sol;
			}
			else lf[x].insert(i);
		}
		else{
			if(!lf[x].empty()){
				a[++NR] = {*lf[x].begin(), i};
				lf[x].erase(lf[x].begin());
			}
			else rf[x].insert(i);
		}
	}

	sort(a + 1, a + NR + 1);
	//cerr << n;
	build();
	
	for(int i = 1; i <= NR ; ++i){
		int p1 = 2 * i - 1, p2 = 2 * i;
		
		int x = query(a[i].x);
		Sol = Sol + abs(x - p1); 
		update(1, a[i].x, 1);

		int y = query(a[i].y);
		Sol = Sol + abs(y - p2);
		update(1, a[i].y, 1);
	}
	
	return Sol;
}

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