Submission #1057412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057412		kkkkkkkk	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	158 ms	142560 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

long long tree[800005];

void update(int k, int left, int right, int poz) {
    if (left==right) {
        if (left==poz)
            tree[k]++;
        return;
    }
    if (left>right||left>poz||right<poz)
        return;
    int mid=(left+right)/2;
    update(2*k, left, mid, poz);
    update(2*k+1, mid+1, right, poz);
    tree[k]=tree[2*k]+tree[2*k+1];
}

long long query(int k, int left, int right, int l, int r) {
    if (left>right||left>r||right<l)
        return 0;
    if (l<=left&&right<=r)
        return tree[k];
    int mid=(left+right)/2;
    long long r1=query(2*k, left, mid, l, r);
    long long r2=query(2*k+1, mid+1, right, l, r);
    return r1+r2;
}

long long count_swaps(vector<int> a) {
    int n=a.size()/2;
    queue<int> q[2*n+5];
    long long rez=0;
    for (int i=0;i<2*n;i++) {
        int golemina=a[i], obr;
        if (golemina<0) golemina=n-a[i], obr=-a[i];
        else obr=n+a[i];
        if (q[obr].empty()) {
            q[golemina].push(i);
            update(1, 0, 2*n-1, i);
        }
        else {
            rez+=query(1, 0, 2*n-1, q[obr].front()+1, i)+(a[i]<0);
            update(1, 0, 2*n-1, q[obr].front());
            q[obr].pop();
        }
    }
    return rez;
}

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