Submission #249276

#	Time	Username	Problem	Language	Result	Execution time	Memory
249276		muhammad_hokimiyon	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	556 ms	148984 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

#define fi first
#define se second
#define ll long long
#define dl double long

using namespace std;

const int NN = 1e9 + 7;
const int N = 2e6 + 7;
const int M = 26;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;
const int B = sqrt(N);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d[N];

void upd( int x , int y )
{
    while( x < N ){
        d[x] += y;
        x += x & -x;
    }
}

int get( int x )
{
    int cnt = 0;
    while( x > 0 ){
        cnt += d[x];
        x -= x & -x;
    }
    return cnt;
}

map < int , deque < int > > m;

long long count_swaps(vector<int> s)
{
    int n = (int)s.size();
    ll ans = 0;
    for( int i = 0; i < n; i++ ){
        m[s[i]].push_back(i + 1);
    }
    vector < int > used(n + 1 , 0);
    for( int i = 0; i < n; i++ ){
        if( used[i] )continue;
        int l = m[s[i]].front();
        int r = m[-s[i]].front();
        m[s[i]].pop_front();
        m[-s[i]].pop_front();
        ans += r - l - (s[i] < 0) - get( r ) + get( l );
        upd( r , 1 );
        used[l - 1] = used[r - 1] = 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