Submission #1082118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082118		logangd	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	106 ms	19664 KiB

shoes

#include "shoes.h"
using namespace std;

vector<int>p[300005],a(800005);

void bld(int nd,int l,int r){
    if(l==r)return a[nd]=1,void();
    int md=(l+r)/2;
    bld(nd*2,l,md);
    bld(nd*2+1,md+1,r);
    a[nd]=a[nd*2]+a[nd*2+1];
}
void res(int p,int nd,int l,int r){
    if(l==r)return a[nd]=0,void();
    int md=(l+r)/2;
    if(p<=md)res(p,nd*2,l,md);
    else res(p,nd*2+1,md+1,r);
    a[nd]=a[nd*2]+a[nd*2+1];
}
int qry(int p,int q,int nd,int l,int r){
    if(q<l||r<p)return 0;
    if(p<=l&&r<=q)return a[nd];
    int md=(l+r)/2;
    return qry(p,q,nd*2,l,md)+qry(p,q,nd*2+1,md+1,r);
}

long long count_swaps(vector<int>s){
    int n=s.size();
    bld(1,0,n-1);
    for(int i=n-1;0<=i;i--)p[s[i]+n].push_back(i);
    long long r=0;
    for(int i=0;i<n;i++){
        if(p[s[i]+n].size()==0||p[s[i]+n].back()!=i)continue;
        res(p[s[i]+n].back(),1,0,n-1);
        p[s[i]+n].pop_back();
        r+=qry(i,p[n-s[i]].back(),1,0,n-1);
        if(s[i]<0)r--;
        res(p[n-s[i]].back(),1,0,n-1);
        p[n-s[i]].pop_back();
    }
	return r;
}

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