Submission #415530

#	Time	Username	Problem	Language	Result	Execution time	Memory
415530		xyz	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	759 ms	27080 KiB

shoes

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

const int N = 2e5 + 20;
int t[4 * N];

void inc(int v, int tl, int tr, int l, int r){
    if(l > r)
        return;
    if(tl == l && tr == r){
        t[v] ++;
        return;
    }
    int tm = (tl + tr) / 2;
    inc(v * 2, tl, tm, l, min(r, tm));
    inc(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
}

void build(int v, int tl, int tr){
    if(tl == tr){
        t[v] = tl;
        return;
    }
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
}

int get(int v, int tl, int tr, int pos){
    if(tl == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    if(pos <= tm)
        return get(v * 2, tl, tm, pos) + t[v];
    else
        return get(v * 2 + 1, tm + 1, tr, pos) + t[v];
}

ll count_swaps(vector<int> s) {
	int n = s.size();
	map<int, vector<int>> m;
	for(int i = n - 1; i >= 0; i --)
        m[s[i]].push_back(i);
	build(1, 0, n - 1);
	ll result = 0;
	for(int i = 0; i < n; i ++){
        if(m[s[i]].empty() || m[s[i]].back() != i)
            continue;
        int j = m[-s[i]].back();
        m[s[i]].pop_back();
        m[-s[i]].pop_back();
        int x = get(1, 0, n - 1, i);
        int y = get(1, 0, n - 1, j);
//        cout << i << " " << j << " : " << x << " " << y << endl;
        result += (y - x) - 1;
        if(s[i] > 0)
            ++ result;
        inc(1, 0, n - 1, i, j);
	}
//	cout << result << endl;
	return result;
}

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