Submission #1215797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215797		horka	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	349 ms	31216 KiB

shoes

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

using ll = long long;

const ll maxN = 2e5+5;


ll segtree[800001];

ll query(ll v, ll vl, ll vr, ll ql, ll qr) {
	if (ql > qr) return 0;
	if (vr == qr && vl == ql) return segtree[v];
	ll mid = (vl + vr) / 2;

	return query(v*2, vl, mid, ql, min(qr, mid)) + query(v*2 + 1, mid + 1, vr, max(mid + 1, ql), qr);
}

void update(ll v, ll vl, ll vr, ll pos, ll val) {
	if (vl == vr) segtree[v] += val;
	else {
		ll mid = (vl + vr) / 2;
		if (pos <= mid) {
			update(v*2, vl, mid, pos, val);
		}
		else{
			update(v*2 + 1, mid + 1, vr, pos, val);
		}
		segtree[v] = segtree[v*2] + segtree[v*2 + 1];
	}
}

long long count_swaps(vector <int> v){

	ll n = v.size();
    map<ll, vector<ll> > Neg, Pos;

	for(ll i = 0; i < n; i++){
   		if(v[i] < 0) Neg[- v[i]].push_back(i+1);
   		else Pos[v[i]].push_back(i+1);
    }
    ll res = 0;


    vector<ll> ind(maxN, 0);
    vector<bool> volt(n+1, 0);

    vector<pair<ll, ll> > pairs;
    for(ll i = 0; i < n; i++) {
        if(volt[i]) continue;
    	ll val = abs(v[i]);

    	ll x = Neg[val][ind[val]];
    	ll y = Pos[val][ind[val]++];
    	
    	volt[x-1] = volt[y-1] = 1;

    	pairs.push_back({min(x, y), max(x, y)});

        if(x < y) {
            res += y-x-1;
        }
        else {
            res += x-y;
        }
    }

    
    ll over = 0;
	for(auto p : pairs) {
        over += query(1, 1, n, p.first, p.second);
        update(1, 1, n, p.second, 1);
    }

	return res - over;
}

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