Submission #200470

#	Time	Username	Problem	Language	Result	Execution time	Memory
200470		Leonardo_Paes	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	90 ms	5612 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;

typedef long long ll;
typedef pair<int,int> pii;

int n, mark[maxn];

ll bit[maxn];

ll sum(int x){
    ll res = 0;
    while(x>0){
        res += bit[x];
        x -= (x&-x);
    }
    return res;
}

void upd(int x, int v){
    while(x<maxn){
        bit[x] += v;
        x += (x&-x);
    }
}

ll count_swaps(vector<int> s){
    n = s.size();

    ll ans = 0LL;

    vector<pii> l, r;

    for(int i=0; i<n; i++){
        mark[abs(s[i])]++;
        if(mark[abs(s[i])]&1){
            l.push_back({abs(s[i]), i});
            if(s[i] > 0) ans++;
        }
        else{
            r.push_back({abs(s[i]), i});
        }
    }

    sort(l.begin(), l.end());
    sort(r.begin(), r.end());

    for(int i=0; i<l.size(); i++){
        r[i].first = l[i].second;
        l[i].first = l[i].second;
    }

    sort(l.begin(), l.end());
    sort(r.begin(), r.end());

    int tt = 0;

    for(int i=0; i<l.size(); i++){
        s[l[i].second] = ++tt;
        s[r[i].second] = ++tt;
    }

    for(int i=0; i<n; i++){
        upd(s[i], 1);
        ans += sum(n) - sum(s[i]);
    }

    return ans;
}

/*int main(){
    int n;

    cin >> n;

    vector<int> s;

    while(n--){
        int x;
        cin >> x;
        s.push_back(x);
    }

    cout << count_swaps(s) << endl;
}*/

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<l.size(); i++){
                  ~^~~~~~~~~
shoes.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<l.size(); i++){
                  ~^~~~~~~~~

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