Submission #822839

#	Time	Username	Problem	Language	Result	Execution time	Memory
822839		vjudge1	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	742 ms	153652 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std ;
const ull N = (1 << 18) ;
ull sum[2 * N + 1], psh[2 * N + 1] ;
void push(ull l, ull r, ull v)
{
    if(!psh[v])
        return ;
    ull num = psh[v] ;
    psh[v] &= 0 ;
    sum[v] += num * (r - l + 1) ;
    if(l == r)
        return ;
    psh[v * 2] += num ;
    psh[v * 2 + 1] += num ;
}
void update(ull l, ull r, ull l1, ull r1, ull num, ull v)
{
    push(l, r, v) ;
    if(l > r1 || r < l1)
        return ;
    if(l1 <= l && r <= r1)
    {
        psh[v] = num ;
        push(l, r, v) ;
        return ;
    }
    ull mid = (l + r) >> 1 ;
    update(l, mid, l1, r1, num, v * 2) ;
    update(mid + 1, r, l1, r1, num, v * 2 + 1) ;
    sum[v] = sum[v * 2] + sum[v * 2 + 1] ;
}
ull get_sum(ull l, ull r, ull ind, ull v)
{
    push(l, r, v) ;
    if(l > ind || r < ind)
        return 0 ;
    if(l == r)
        return sum[v] ;
    ull mid = (l + r) >> 1 ;
    return get_sum(l, mid, ind, v * 2) + get_sum(mid + 1, r, ind, v * 2 + 1) ;
}
ll count_swaps(vector<int> v)
{
    map<int, deque<int>> mp ;
    ull ans = 0, n = v.size() ;
    bool us[n + 1] = {} ;
    for(ull i = 0 ; i < n ; i++)
        mp[v[i]].push_back(i) ;
    for(ull i = 0 ; i < n ; i++)
    {
        if(us[i])
            continue ;
        ull ind1 = i, ind2 = mp[-v[i]][0] ;
        us[ind1] = 1 ;
        us[ind2] = 1 ;
        mp[v[i]].pop_front() ;
        mp[-v[i]].pop_front() ;
        update(0, N - 1, ind1 + 1, ind2 - 1, 1, 1) ;
        ind1 += get_sum(0, N - 1, ind1, 1) ;
        ind2 += get_sum(0, N - 1, ind2, 1) ;
        if(v[i] > 0)
            ans += ind2 - ind1 ;
        else
            ans += ind2 - ind1 - 1 ;
    }
    return ans ;
}
//signed main()
//{
//    ios_base::sync_with_stdio( 0 ) ;
//    cin.tie( 0 ) ;
//    cout.tie( 0 ) ;
//    ull n ;
//    cin >> n ;
//    vector<ull> v(n) ;
//    for(ull i = 0 ; i < n ; i++)
//        cin >> v[i] ;
//    cout << count_swaps(v) ;
//    return 0 ;
//}

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