Submission #532995

#	Time	Username	Problem	Language	Result	Execution time	Memory
532995		gun_gan	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	54 ms	19344 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

template <typename T>
struct Fenwick {
    vector<T> t;
    T n;
    Fenwick(T n) : n(n) {
        t.resize(n);
    }
    T g(T r){
        T ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += t[r];
        return ret;
    }
    T sum(T l, T r){
        return g(r) - g(l - 1);
    }
    void add(T i, T v){
        for(;i < n; i = i | (i + 1))
            t[i] += v;
    }

    void range_add(T l, T r, T v){
    	add(l, v);
    	add(r + 1, -v);
    }
};

long long count_swaps(vector<int> s){
	long long n = s.size(), ans = 0;
	const int N = 1e5;
	vector<int> p[2 * N + 100];
	for(int i=0;i<n;i++)
	{
		p[s[i] + N].push_back(i);
	}
	Fenwick<long long> fw(n + 100);
	vector<bool> vis(2 * N);
	for(int i=0;i<n;i++)
	{
		if(vis[i]) continue;
		int pos = *lower_bound(p[-s[i] + N].begin(), p[-s[i] + N].end(), i + 1);
		// for(auto i : vis) cerr << i << " "; cerr << '\n';
		ans += (pos + fw.g(pos)) - (i + 1 + fw.g(i + 1)); 
		vis[pos + fw.g(pos)] = 1;
		vis[i] = 1;
		fw.range_add(i+1, pos, 1);
		if(s[i] > s[pos])
		{
			ans += 1;
		}
	}
	return ans;
}


// signed main(){
// 	int n;
// 	cin >> n;
// 	vector<int> t(2*n);
// 	for(int i=0;i<2*n;i++) cin >> t[i];
// 	cout << count_swaps(t) << '\n';
// }

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