Submission #485926

#	Time	Username	Problem	Language	Result	Execution time	Memory
485926		status_coding	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	327 ms	21928 KiB

shoes

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

using namespace std;

vector<int> seg;
map<int, vector<int>[2]> fr;

void afis(int st, int dr, int p)
{
    cout<<st<<' '<<dr<<' '<<seg[p]<<'\n';

    if(st == dr)
        return;

    int mij=(st+dr)/2;
    afis(st, mij, 2*p);
    afis(mij+1, dr, 2*p+1);
}

void upd(int i, int st, int dr, int p, int val)
{
    if(st == dr)
    {
        seg[p]=val;
        return;
    }

    int mij=(st+dr)/2;

    if(i <= mij)
        upd(i, st, mij, 2*p, val);
    else
        upd(i, mij+1, dr, 2*p+1, val);

    seg[p]=seg[2*p] + seg[2*p+1];
}

long long query(int stt, int drt, int st, int dr, int p)
{
    if(stt>drt)
        return 0;

    if(stt == st && drt == dr)
        return seg[p];

    int mij=(st+dr)/2;

    if(drt<=mij)
        return query(stt, drt, st, mij, 2*p);
    if(stt>mij)
        return query(stt, drt, mij+1, dr, 2*p+1);

    return query(stt, mij, st, mij, 2*p) +
            query(mij+1, drt, mij+1, dr, 2*p+1);
}

long long count_swaps(vector<int> v)
{
    int n=v.size();
    seg.resize(4*n + 4);

    for(int i=(int)v.size()-1;i>=0;i--)
    {
        int tip = v[i] > 0 ? 1 : 0;
        int x=abs(v[i]);

        fr[x][tip].push_back(i);
        upd(i, 0, n-1, 1, 1);
    }

    long long ans=0;
    for(int i=0;i<(int)v.size();i++)
    {
        int tip = v[i] > 0 ? 1 : 0;
        int x=abs(v[i]);

        if(fr[x][tip].empty() || fr[x][tip].back() != i)
            continue;

        int per = fr[x][1-tip].back();

        //cout<<i<<' '<<per<<'\n';

        ans += query(i+1, per-1, 0, n-1, 1);
        ans += tip;

        fr[x][1-tip].pop_back();
        fr[x][tip].pop_back();

        upd(per, 0, n-1, 1, 0);
    }

    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