Submission #870783

#	Time	Username	Problem	Language	Result	Execution time	Memory
870783		tien9d2	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	128 ms	19032 KiB

shoes

#include <bits/stdc++.h>
#define ll pair<int,int>
using namespace std;

const int N=100001;
int base=100001;
vector<int> vt[N*2];
long long k[N*2];////xét đến cái thứ bao nhiêu của vector vt :D
long long tree[N*8];

void update(int s,int l,int r,int u,int kk)
{
    if ((l>r) or (l>u) or (r<u))
    {
        return;
    }
    if (l==r)
    {
        tree[s]+=kk;
        return;
    }
    int mid=(l+r)>>1;
    update(s*2,l,mid,u,kk);
    update(s*2+1,mid+1,r,u,kk);
    tree[s]=tree[s*2]+tree[s*2+1];
}

long long getval(int s,int l,int r,int u,int v)
{
    if ((l>r) or (l>v) or (r<u)) return 0;
    if ((u<=l) and (r<=v))
    {
        return tree[s];
    }
    int mid=(l+r)>>1;
    return getval(s*2,l,mid,u,v)+getval(s*2+1,mid+1,r,u,v);
}

long long count_swaps(vector<int> S)
{
    // freopen("COCKTAIL.INP","r",stdin);
    // freopen("COCKTAIL.OUT","w",stdout);
    // ios_base::sync_with_stdio(0);
    // cin.tie(NULL);
    // cout.tie(NULL);
    int n=S.size()/2;
    // cin >> n;
    for (int i=1;i<=n*2;i++)
    {
        // cin >> a[i];
        vt[S[i-1]+base].push_back(i);
    }
    for (int i=1;i<=n*2;i++)
    {
        update(1,1,n*2,i,1);
    }
    long long kq=0;
    // long long bef=0;
    for (int i=1;i<=n*2;i++)
    {
        if (S[i-1]>0)
        {
            if (vt[S[i-1]+base][k[S[i-1]+base]]!=i) continue;
            int kk=0-S[i-1]+base;
            int i2=vt[kk][k[kk]];
            k[kk]++;
            k[S[i-1]+base]++;
            if (i<i2) kq+=getval(1,1,n*2,i,i2)-1;
            else kq+=getval(1,1,n*2,i2,i)-2;
            update(1,1,n*2,i2,-1);
            update(1,1,n*2,i,1);
            //cout << i2 << " " << kq-bef << '\n';
            // bef=kq;
        }
        else
        {
            if (vt[S[i-1]+base][k[S[i-1]+base]]!=i) continue;
            int kk=0-S[i-1]+base;
            int i2=vt[kk][k[kk]];
            k[kk]++;
            k[S[i-1]+base]++;
            if (i<i2) kq+=getval(1,1,n*2,i,i2)-2;
            else kq+=getval(1,1,n*2,i2,i)-1;
            update(1,1,n*2,i2,-1);
            update(1,1,n*2,i,1);
            //cout << i2 << " " << kq-bef << '\n';
            // bef=kq;
        }
    }
    //cout << kq;
    return kq;
}

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