Submission #382123

#	Time	Username	Problem	Language	Result	Execution time	Memory
382123		ritul_kr_singh	Arranging Shoes (IOI19_shoes)	C++17	25 / 100	99 ms	9580 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 val, 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] += val);
		int mx = (lx+rx)/2;
		update(val, l, r, 2*x+1, lx, mx);
		update(val, l, r, 2*x+2, mx, rx);
	}
	void update(int val, int l, int r){ update(val, 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>> pos(n);
	for(int i=2*n-1; i>=0; --i){
		if(s[i]>0) pos[s[i]-1].push_back(i);
	}
	long long ans = 0;
	for(int i=0; i<2*n; ++i){
		if(s[i]<0){
			int curr = -s[i]-1;
			int p = pos[curr].back();
			int i_ = st.get(i), p_ = st.get(p);
			if(i_<p_){
				ans += (long long)(p_-i_-1);
				st.update(1, i, p);
			}else{
				ans += (long long)(i_-p_);
			}
			pos[curr].pop_back();
		}
	}
	return ans;
}

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