Submission #584420

#	Time	Username	Problem	Language	Result	Execution time	Memory
584420		Valters07	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	603 ms	146612 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#pragma GCC optimize("O2,unroll-loops")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
#define r0 return 0;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5+5;
int f[N];
void add(int pos, int val)
{
    pos++;
    while(pos<N)
        f[pos]+=val,
        pos+=(pos&(-pos));
}
int sum(int pos)
{
    int ret = 0;
    while(pos)
        ret+=f[pos],
        pos-=(pos&(-pos));
    return ret;
}
int sum_seg(int l, int r)
{
    l++,r++;
    return sum(r)-sum(l-1);
}
ll count_swaps(vector<int> ve)
{
    int n = ve.size();
    map<int,queue<int> > mp;
    for(int i = 0;i<n;i++)
        mp[ve[i]].push(i);
    ll ans = 0;
    for(int i = 0;i<n;i++)
    {
        if(mp[ve[i]].empty()||mp[ve[i]].front()!=i)
            continue;
        int p1 = i, p2 = mp[-ve[i]].front();
        mp[ve[i]].pop();
        mp[-ve[i]].pop();
        ans+=(p2-p1-1)+(ve[i]>0)-sum_seg(p1,p2);
        add(p2,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