Submission #200492

#	Time	Username	Problem	Language	Result	Execution time	Memory
200492		Leonardo_Paes	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	340 ms	191568 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;

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, ll v){
    while(x<maxn){
        bit[x] += v;
        x += (x&-x);
    }
}

deque<int> d[maxn];

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

    ll ans = 0LL;

    vector<pii> l, r;

    for(int i=0; i<n; i++){
        if(!d[abs(s[i])].empty() and d[abs(s[i])].back() != s[i]){
            d[abs(s[i])].pop_back();
            r.push_back({abs(s[i]), i});
            if(s[i] < 0) ans++;
        }
        else{
            d[abs(s[i])].push_front(s[i]);
            l.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], 1LL);
        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:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<l.size(); i++){
                  ~^~~~~~~~~
shoes.cpp:63: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: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15