Submission #156155

#	Time	Username	Problem	Language	Result	Execution time	Memory
156155		wildturtle	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	99 ms	76636 KiB

shoes

#include "shoes.h"
long long a,b,c,d,i,e,f,g,n,m,k,l,ans,idx,tree[800005],fix[800005],A[800005],B[800005],le,ri;
std::vector <long long> L[800005],R[800005];
void upd(long long node,long long tl,long long tr,long long pos){
	if(tl==tr) { tree[node]=1; return; }
	long long mid=(tl+tr)/2;
	if(pos<=mid) upd(node*2,tl,mid,pos);
	else upd(node*2+1,mid+1,tr,pos);
	tree[node]=tree[node*2]+tree[node*2+1];
}
long long get(long long node,long long tl,long long tr){
	if(ri<tl || tr<le) return 0;
	if(tr<=ri && le<=tl) return tree[node];
	long long mid=(tr+tl)/2;
	long long x=get(node*2,tl,mid);
	long long y=get(node*2+1,mid+1,tr);
	return x+y;
}
long long count_swaps(std::vector<int> s) {
           n=s.size();
           for(long long i=0;i<n;i++) {
                      if(s[i]<0) {
                                 L[-s[i]].push_back(i);
                      }
                      else {
                                 R[s[i]].push_back(i);
                      }
           }
           for(long long i=0;i<n;i++) {
                      if(fix[i]==0) {
                                 if(s[i]<0) {
                                            idx=L[-s[i]][A[-s[i]]];
                                            ri=idx;
                                            le=i;
                                            ans+=(ri-le-1-get(1,0,n-1));
                                            A[-s[i]]++;
                                            B[-s[i]]++;
                                            fix[idx]++;
                                            upd(1,0,n-1,idx);
                                 }
                                 else {
                                            idx=R[s[i]][B[s[i]]];   
                                            ri=idx;
                                            le=i;
                                            ans+=(ri-le-get(1,0,n-1));
                                            A[s[i]]++;
                                            B[s[i]]++;
                                            fix[idx]++;
                                            upd(1,0,n-1,idx);
                                 }
                      }
           }
           return ans;
}

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