Submission #382205

#	Time	Username	Problem	Language	Result	Execution time	Memory
382205		ritul_kr_singh	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	158 ms	16236 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
#define nl << "\n"
 
struct segtree{
	int sz = 1;
	vector<int> a;
	segtree(int n){
		while(sz < n) sz *= 2;
		a.assign(2*sz, 0);
	}
	void update(int l, int r, int x, int lx, int rx){
		if(rx<=l or r<=lx) return;
		if(l<=lx and rx<=r) return void(++a[x]);
		int mx = (lx+rx)/2;
		update(l, r, 2*x+1, lx, mx);
		update(l, r, 2*x+2, mx, rx);
	}
	void update(int l, int r){ update(l, r, 0, 0, sz); }
	int get(int i, int x, int lx, int rx){
		if(rx-lx==1) return a[x];
		int mx = (lx+rx)/2;
		if(i<mx) return a[x] + get(i, 2*x+1, lx, mx);
		else return a[x] + get(i, 2*x+2, mx, rx);
	}
	int get(int i){ return i+get(i, 0, 0, sz); }
};
 
long long count_swaps(vector<int> s){
	int n = ((int)s.size())/2;
	segtree st(2*n);
 
	vector<vector<int>> pos0(n), pos1(n);
	for(int i=2*n-1; i>=0; --i){
		if(s[i]>0) pos1[s[i]-1].push_back(i);
		else pos0[-s[i]-1].push_back(i);
	}
	long long ans = 0;
	for(int i=0; i<2*n; ++i){
		int curr = abs(s[i])-1;
		if((pos0[curr].empty() or pos0[curr].back()!=i)
			and (pos1[curr].empty() or pos1[curr].back()!=i)) continue;
		int p = s[i] > 0 ? pos0[curr].back() : pos1[curr].back();
		int i_ = st.get(i), p_ = st.get(p);
		ans += (long long)(p_-i_-(s[i]<0));
		st.update(i, p);
		pos0[curr].pop_back();
		pos1[curr].pop_back();
	}
	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