Submission #759031

#	Time	Username	Problem	Language	Result	Execution time	Memory
759031		Trumling	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	276 ms	37644 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std; 
 
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()

ll seg[6000001];

void update (int pos,int l,int r,int idx,int u)
{
    if(pos<l || pos>r)
        return ;
 
    if(l==r)
    {
        seg[idx]=u;
        return ;
    }
    update(pos,l,(l+r)/2,idx*2,u);
    update(pos,(l+r)/2+1,r,idx*2+1,u);
    seg[idx]=seg[idx*2]+seg[idx*2+1];
}
 
ll query(int L,int R,int l,int r,int idx)
{
    if(L>r || R<l)
    return 0;
 
    if(L<=l && r<=R)
    return seg[idx];
 
    return query(L,R,(l+r)/2+1,r,idx*2+1)+query(L,R,l,(l+r)/2,idx*2);
 
}

long long count_swaps(vector<int>s) 
{
	ll nn=s.size();

	map<int,vector<int>>mp;
	for(int i=0;i<nn;i++)
	mp[s[i]].pb(i);

vector<pair<int,pair<int,int>>>g;
vector<int>answ(nn);

for(int j=1;j<=nn;j++)
{
	if(mp[j].empty())
	continue;

	auto x=mp[-j],y=mp[j];

	for(int i=0;i<x.size();i++)
	g.pb({x[i]+y[i]+((x[i]<y[i])?-1:0),{x[i],y[i]}});
}
sort(all(g));

ll idx=0;
for(auto x:g)
{
	answ[x.S.F]=idx++;
	answ[x.S.S]=idx++;
}
ll ans=0;

for(int i=0;i<nn;i++)
{
ans+=query(answ[i],nn-1,0,nn-1,1);
 update(answ[i],0,nn-1,1,1);
}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0;i<x.size();i++)
      |              ~^~~~~~~~~

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