Submission #489963

#	Time	Username	Problem	Language	Result	Execution time	Memory
489963		kevin	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	179 ms	140224 KiB

shoes

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

#define all(x) x.begin(), x.end()
#define ll long long
#define nl cout<<"\n"
#define ca(v) for(auto i:v) cout<<i<<" ";

struct BIT {
    vector<int> f;
    int n;
    void init(int N) { f = vector<int>(N+1, 0); n = N;}
    int lsb(int x) { return x & -x; }
    void update(int p, int v){ 
        while(p <= n){ f[p] += v; p += lsb(p); } 
    }
    int query(int p) { 
        int sum = 0; 
        while (p > 0) { sum += f[p]; p -= lsb(p); } 
        return sum; 
    }
};

ll count_swaps(vector<int> ar){
    int n = ((int)ar.size()) / 2;
    queue<int> pos[n+5][2];
    vector<int> ord;
    vector<int> sz(n+5, 0);
    for(int i=0; i<2*n; i++){
        if(ar[i] < 0) pos[-ar[i]][0].push(i+1);
        else pos[ar[i]][1].push(i+1);
        int pv = sz[abs(ar[i])];
        sz[abs(ar[i])] += (ar[i]>0?1:-1);
        if(abs(sz[abs(ar[i])]) > abs(pv)) ord.push_back(abs(ar[i]));
    }
    BIT fen; fen.init(2*n+10);
    ll ans = 0;
    for(int k=1; k<=n; k++){
        int x = ord[k-1];
        int i = pos[x][0].front(); pos[x][0].pop();
        int j = pos[x][1].front(); pos[x][1].pop();
        if(j<i) { ans++; swap(i, j); }
        ans += (ll) i+fen.query(i) - (2*k-1);
        fen.update(1, 1); fen.update(i, -1);
        ans += (ll)j+fen.query(j) - 2*k;
        fen.update(1, 1); fen.update(j, -1);
    }
    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