Submission #443223

#	Time	Username	Problem	Language	Result	Execution time	Memory
443223		vanic	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	270 ms	273644 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;

const int maxn=2e5+5;

struct logaritamska{
	int l[maxn];
	void update(int x, int val){
		for(; x<maxn; x+=(x & -x)){
			l[x]+=val;
		}
	}
	int query(int x){
		int sol=0;
		for(; x>0; x-=(x & -x)){
			sol+=l[x];
		}
		return sol;
	}
};

logaritamska L;

queue < int > q1[maxn], q2[maxn];

ll count_swaps(vector<int> s){
	int n=s.size();
	ll sol=0;
	int a, b, c, d;
	for(int i=0; i<n; i++){
		if(s[i]>0){
			if(!q2[s[i]].empty()){
				a=q2[s[i]].front();
				q2[s[i]].pop();
				b=i;
				c=L.query(a+1)+a;
				d=L.query(b+1)+b;
				sol+=d-c-1;
				L.update(a+1, 1);
				L.update(b+1, -1);
			}
			else{
				q1[s[i]].push(i);
			}
		}
		else{
			if(!q1[-s[i]].empty()){
				a=q1[-s[i]].front();
				q1[-s[i]].pop();
				b=i;
				c=L.query(a+1)+a;
				d=L.query(b+1)+b;
				sol+=d-c;
				L.update(a+1, 1);
				L.update(b+1, -1);
			}
			else{
				q2[-s[i]].push(i);
			}
		}
	}
	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