Submission #418753

#	Time	Username	Problem	Language	Result	Execution time	Memory
418753		nafis_shifat	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	94 ms	20292 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define ll long long
const int mxn = 2e5+ 5;
using namespace std;


struct BIT {
	int bit[mxn] = {};
	void update(int p,int v) {
		for(; p < mxn; p += p & -p) bit[p] += v;
	}
    int query(int p) {
    	int res = 0;
    	for(; p > 0; p -= p & -p) res += bit[p];
    	return res;
    }
    int query(int a,int b) {
    	if(a > b) return 0;
    	return query(b) - query(a - 1);
    }
} bt;
ll count_swaps(vector<int> s) {
	int n = s.size();
	vector<int> left[n],right[n];

	for(int i = n - 1; i >= 0; i--) {
		if(s[i] < 0) left[-s[i]].push_back(i);
		else right[s[i]].push_back(i);
	}


	int vis[n + 1] = {};
	ll res = 0;
	for(int i = 0; i < n; i++) {


		if(vis[i]) {
			continue;
		}

		if(s[i] < 0) {
			int x = -s[i];
			assert(i == left[x].back());
			left[x].pop_back();

			int y = right[x].back();

			res += y - i - 1 - bt.query(i + 1,y - 1);
			vis[y] = 1;
			
		
			right[x].pop_back();
			bt.update(y,1);

		} else {
			int x = s[i];
			assert(i == right[x].back());
			right[x].pop_back();


			int y = left[x].back();
			res += y - i - bt.query(i + 1,y - 1);
			vis[y] = 1;
		

			left[x].pop_back();
			bt.update(y,1);
		}

		
	}

	return res;
}

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