Submission #596051

#	Time	Username	Problem	Language	Result	Execution time	Memory
596051		alirezasamimi100	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	119 ms	72688 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<int,int>;
#define pb push_back
#define F first
#define S second

const int N = 1e5 + 10;

queue<int> q[N];
vector<pii> pr;
int f[N*2];
ll ans;
void upd(int t, int x){
    for(t+=5; t<N*2; t+=t&-t) f[t]+=x;
}
int get(int t, int x=0){
    for(t+=5; t; t-=t&-t) x+=f[t];
    return x;
}
ll count_swaps(vector<int> s) {
    int n = s.size();
    for(int i=0; i<n; i++){
        int x=abs(s[i]);
        upd(i,1);
        if(q[x].empty() || s[q[x].front()]==s[i]) q[x].push(i);
        else{
            pr.pb({q[x].front(),i});
            q[x].pop();
            if(s[i]!=x) ans++;
        }
    }
    sort(pr.begin(),pr.end());
    for(auto [x,y] : pr){
        upd(x,-1);
        upd(y,-1);
        ans+=get(y);
    }
    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