Submission #249270

#	Time	Username	Problem	Language	Result	Execution time	Memory
249270		muhammad_hokimiyon	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1 ms	384 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 , vector < int > > m;

long long count_swaps(vector<int> s)
{
    int n = (int)s.size();
    ll ans = 0;
    for( int i = 1; i <= n; i++ ){
        int x = -s[i - 1];
        if( m[x].empty() ){
            m[-x].push_back(i);
        }else{
            int y = m[x].back();
            m[x].pop_back();
            ans += i - y - (x < 0) - get( i ) + get( y );
            upd( i + 1 , -1 );
            upd( y , 1 );
        }
    }
    return ans;
}

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