Submission #298217

#	Time	Username	Problem	Language	Result	Execution time	Memory
298217		arayi	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	393 ms	275144 KiB

shoes

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

const int N = 2e5 + 30;
int n;
queue <long long> a[N], b[N];
bool col[N];
long long pat;
int t[4 * N];
void upd(int q, int nl = 0, int nr = n - 1, int nd = 1)
{
    if(q > nr || q < nl) return;
    if(nl == nr)
    {
        t[nd]++;
        return;
    }
    int mid = (nl + nr) / 2;
    upd(q, nl, mid, nd * 2);
    upd(q, mid + 1, nr, nd * 2 + 1);
    t[nd] = t[nd * 2] + t[nd * 2 + 1];
}
int qry(int l, int r, int nl = 0, int nr = n - 1, int nd = 1)
{
    if(l > nr || r < nl) return 0;
    if(l == nl && r == nr) return t[nd];
    int mid = (nl + nr) / 2;
    return qry(l, min(mid, r), nl, mid, nd * 2) + qry(max(mid + 1, l), r, mid + 1, nr, nd * 2 + 1);
}
long long count_swaps(std::vector<int> s) {
    n = s.size();
    for (int i = 0; i < n; i++)
    {
        if(s[i] < 0) b[-s[i]].push(i);
        else a[s[i]].push(i);
    }
    for (int i = 0; i < n; i++)
    {
        if(col[i]) continue;
        int x = abs(s[i]);
        long long l = min(a[x].front(), b[x].front()), r = max(a[x].front(), b[x].front());
        if(a[x].front() > b[x].front()) pat--;
        a[x].pop(), b[x].pop();
        long long sm = qry(l, r);
        pat += r - l - sm;
        col[l] = col[r] = 1;
        upd(r);
    }
	return pat;
}

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