Submission #1196810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196810		MateiKing80	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	127 ms	138948 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;

queue<int> d[2 * MAXN];
bitset<2 * MAXN> v;
long long ft[2 * MAXN];
int N;
void update(int k,long long val) {
    int x = k + 1;
    while (x <= N) {
        ft[x] += val;
        x += x & -x;
    }
}

long long query(int k) {
    int x = k + 1;
    long long s = 0;
    while (x > 0) {
        s += ft[x];
        x -= x & (-x);
    }
    return s;
}

long long count_swaps(vector<int> s) {
    N=s.size();
    long long ans=0;
	  for (int i = 0; i < N; i ++)
	      d[s[i] + MAXN].push(i);
    for (int i = 0; i < N; i ++)
        update(i,1);
    for (int i = 0; i < N; i ++) {
        if(v[i])
            continue;
        d[s[i] + MAXN].pop();
        int h = d[MAXN - s[i]].front();
        d[MAXN - s[i]].pop();
        v[i] = 1;
        v[h] = 1;
        ans += query(h) - query(i) - 1;
        update(i, 1);
        update(h, -1);
        if (s[i] > s[h])
          ans ++;
    }
    return ans;
}

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