Submission #152066

#	Time	Username	Problem	Language	Result	Execution time	Memory
152066		oolimry	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	375 ms	14280 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
 
static int tree[500005];
long long N;
void update(int x){
	x += N;
	while(x > 0){
		tree[x]++;
		x >>= 1;
	}
}
 
long long query(int l, int r){
	long long ans = 0;
	for(l += N, r += N;l < r;l >>= 1, r >>= 1){
		if(l&1){
			ans += tree[l];
			l++;
		}
		if(r&1){
			r--;
			ans += tree[r];
		}
	}
	return ans;
}
long long count_swaps(std::vector<int> s) {
	long long n = s.size() / 2;
	N = 2 * n;
	long long ans = 0;
	
	set<long long> things;
	for(int i = 0;i < 2 * n;i++){
		if(s[i] < 0) s[i] = (s[i] * -1) - 1;
		else s[i] = s[i] - 1 + n;
		
		long long ss = s[i] * 1000000ll;
		things.insert(ss + i);
	}
	
	
	//for(int i = 0;i < 2 * n;i++) cout << nxt[i] << " ";
	int pos = 0;
	
	for(int i = 0;i < 2 * n;i++){
		
		if(query(i,i+1) != 0) continue;
		
		int x = s[i];
		int y = 0;
		if(x < n) y = x + n;
		else y = x - n;
		
		int l = i;
		//if(stuff[y].empty()) while(true) continue;
		long long rr = *things.lower_bound(y * 1000000ll);
		int r = rr % 1000000;
		//int r = stuff[y].front();
		//stuff[y].pop();
		//if(stuff[x].empty()) while(true) continue;
		//stuff[x].pop();
		
		
		
		int nl = l + query(l+1,2*n); 
		int nr = r + query(r+1,2*n); 
		//cout << i << " " << l << " " << r << " " << nl << " " << nr << " " << ans << "\n";
		if(x < n){
			ans += (nl - 2 * pos);
			ans += (nr - (2 * pos + 1));
		}
		else{
			ans += (nr - 2 * pos);
			ans += (nl - (2 * pos + 1));
			ans++;
		}
		
		pos++;
		
		update(l);
		update(r);
		things.erase(rr);
		//long long 
		things.erase(x * 1000000ll + i);
	}
	
	
 
	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