Submission #1031029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031029		Maite_Morale	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	544 ms	190672 KiB

shoes

#include <cstdio>
#include <cassert>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>


struct ABI{
	vll sum;
	ABI(ll n){
		sum.assign(n*2+5,0);
	}
	void update(ll a,ll b){
		for(a;a<sum.size();a+=(a&-a))sum[a]+=b;
	}
	ll query(ll a){
		ll r=0;
		for(a;a>0;a-=(a&-a))r+=sum[a];
	return r;
	}
};
long long count_swaps(std::vector<int> s){
	ll c=0;vll a(s.size()+50,0);
	map<ll,ll> mp;vector<queue<int>> v={};
	for(int i=0;i<s.size();i++){
		s[i]*=-1;
		if(mp[s[i]]==0){
			v.push_back({});
			c++;mp[s[i]]=c;
		}
		v[mp[s[i]]-1].push(i+1);
	}
	ABI abi(s.size()+5);ll r=0;
	for(int i=1;i<=s.size();i++){
		ll d=s[i-1];
		//cerr<<d<<": ";
		if(v[mp[d]-1].size()!=0 && a[i-1]==0){
		//	cerr<<"^\n";
			if(d<0)r+=1;
			abi.update(v[mp[-d]-1].front(),1);
			abi.update(v[mp[ d]-1].front(),1);
			r+=v[mp[-d]-1].front()-abi.query(v[mp[-d]-1].front());
			a[v[mp[-d]-1].front()-1]=a[i-1]=1;
			v[mp[-d]-1].pop();
			v[mp[ d]-1].pop();
		}
		//cerr<<r<<"\n";
	}
return r;
}

Compilation message (stderr)

shoes.cpp: In member function 'void ABI::update(ll, ll)':
shoes.cpp:15:7: warning: statement has no effect [-Wunused-value]
   15 |   for(a;a<sum.size();a+=(a&-a))sum[a]+=b;
      |       ^
shoes.cpp:15:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for(a;a<sum.size();a+=(a&-a))sum[a]+=b;
      |         ~^~~~~~~~~~~
shoes.cpp: In member function 'll ABI::query(ll)':
shoes.cpp:19:7: warning: statement has no effect [-Wunused-value]
   19 |   for(a;a>0;a-=(a&-a))r+=sum[a];
      |       ^
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~
shoes.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i=1;i<=s.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