Submission #487155

#	Time	Username	Problem	Language	Result	Execution time	Memory
487155		M_W	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	160 ms	139572 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
queue<int> q[100001], q2[100001];
bool mark[200001];

int fwt[200001];

void ins(int v, int a){
	for(; v <= 200000; v += (v & -v)) fwt[v] += a;
}

int query(int v){
	int ret = 0;
	for(; v > 0; v -= (v & -v)) ret += fwt[v];
	return ret; 
}

long long count_swaps(vector<int> S){
	int len = S.size();
	S.insert(S.begin(), 0);
	for(int i = 1; i <= len; i++){
		ins(i, 1); ins(i + len, 1);
		if(S[i] > 0) q[S[i]].push(i);
		else q2[-S[i]].push(i);
	}
	long long ans = 0;
	for(int i = 1; i <= len; i++){
		if(mark[i]) continue;
		mark[i] = true;
		if(S[i] < 0){
			q2[-S[i]].pop();
			
			ans += query(q[-S[i]].front() - 1) - query(i);
			ins(q[-S[i]].front(), -1);
			
			mark[q[-S[i]].front()] = true;
			q[-S[i]].pop();
		}
		else{
			q[S[i]].pop();
			
			ans += query(q2[S[i]].front() - 1) - query(i) + 1;
			ins(q2[S[i]].front(), -1);
			
			mark[q2[S[i]].front()] = true;
			q2[S[i]].pop();
		}
	}
	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