Submission #1215827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215827		sangeraf	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	258 ms	39552 KiB

shoes

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

using ll = long long;

const ll maxN = 2e5+5;

vector<ll> t;

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

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

void update(ll v, ll tl, ll tr, ll pos, ll new_val) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        ll tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = t[v*2] + t[v*2+1];
    }
}

ll count_swaps(vector<int>v){
    ll n = v.size();
    t.assign(4*n+5, 0);
    build(1, 1, n);

    map<ll, vector<ll> > m;
    for(ll i = 0; i < n; i++) {
        m[v[i]].push_back(i+1);
    }

    
    ll res = 0;
    vector<pair<ll, ll> > pairs;
    for(ll i = 0; i < maxN; i++) {
        for(ll j = 0; j < (ll)m[i].size(); j++) {
            pairs.push_back({m[-i][j], m[i][j]});
            if(m[-i][j] > m[i][j]) {
                swap(pairs.back().first, pairs.back().second);
				res++;
            }
        }
    }
    sort(pairs.begin(), pairs.end());
    for(auto p : pairs) {
        res += sum(1, 1, n, p.first+1, p.second-1);
        update(1, 1, n, p.second, 0);
    }
    return res;
}

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