Submission #697368

#	Time	Username	Problem	Language	Result	Execution time	Memory
697368		nasir_bashirov	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	35 ms	8592 KiB

shoes

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

struct segTree{
    int n;
    vector<long long> t;
    segTree(int sz){
        n = sz;
        t.resize((n + 1) << 1, 0);
    }
    void sett(int i, int val){
        t[i + n - 1] = val;
    }
    void build(){
        for(int i = n - 1; i >= 1; i--){
            t[i] = t[i << 1] + t[i << 1 | 1];
        }
    }
    void update(int i, int val){
        for(t[i += n - 1] = val; i > 1; i >>= 1){
            t[i >> 1] = t[i] + t[i ^ 1];
        }
    }
    long long query(int l, int r){
        long long res = 0;
        for(l += n - 1, r += n; l < r; l >>= 1, r >>= 1){
            if(l & 1)   res += t[l++];
            if(r & 1)   res += t[--r];
        }
        return res;
    }
};

long long count_swaps(std::vector<int> s) {
	int n = s.size(), k = 0;
	pair<int, int> a[n];
	vector<int> used(n + 1, 0);
	segTree st(n);
	long long res = 0;
	for(int i = 1; i <= n; i++){
		if(!used[abs(s[i - 1])]){
			used[abs(s[i - 1])] = i;
		}
		else{
			k++;
			a[k] = {used[abs(s[i - 1])], i};
		}
		st.sett(i, 1);
	}
	st.build();
	for(int i = 1; i <= n / 2; i++){
		res += st.query(a[i].first + 1, a[i].second - 1);
		if(s[a[i].second - 1] < 0)	res++;
		st.update(a[i].first, 0);
		st.update(a[i].second, 0);
	}
	return res;
}

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