Submission #1167615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167615		InvMOD	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	374 ms	24708 KiB

shoes

#include<bits/stdc++.h>

//#define name "InvMOD"
#ifndef name
    #include "shoes.h"
#endif // name

using namespace std;

#define sz(v) (int)(v).size()

using ll = long long;

// 2i : left shoe, 2i + 1: right shoe
// x < 0 -> left shoe, x > 0 -> right shoe

struct BIT{
    vector<int> bit;
    BIT(int n = 0): bit(n + 1) {}

    void update(int p, int val){
        for(; p < sz(bit); p += (p & (-p))){
            bit[p] += val;
        }
        return;
    }

    int get(int p){
        if(p < 0) return 0;
        int res = 0;
        for(; p > 0; p -= (p & (-p))){
            res += bit[p];
        }
        return res;
    }

    int query(int l, int r){
        if(l > r) return 0;
        return get(r) - get(l - 1);
    }
};

ll count_swaps(vector<int> S){
    BIT bit(sz(S)); map<int, vector<int>> ppos;
    for(int i = sz(S) - 1; i >= 0; i--)
        ppos[S[i]].push_back(i);

    vector<bool> vis(sz(S), false);

    ll answer = 0;
    for(int i = 0; i < sz(S); i++){
        if(!sz(ppos[S[i]]) || ppos[S[i]].back() != i) continue;

        int nxt_pos = ppos[-S[i]].back();
        answer = answer + (nxt_pos - i - (S[i] < 0)) - bit.query(i + 1, nxt_pos);

        bit.update(nxt_pos, 1);
        ppos[-S[i]].pop_back(), ppos[S[i]].pop_back();
    }
    return answer;
}

#ifdef name
    int32_t main(){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);

        int n; cin >> n;

        vector<int> S(2 * n);
        for(int i = 0; i < 2 * n; i++){
            cin >> S[i];
        }

        cout << count_swaps(S) << "\n";
        return 0;
    }
#endif // name

/*
Input:
2
2 1 -1 -2

Ex:
2 1 -2 -1
2 -2 1 -1
-2 2 1 -1
-2 2 -1 1

Input:
3
-2 2 2 -2 -2 2

*/

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