Submission #1030996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030996		Maite_Morale	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	1 ms	348 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++){
			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:8: warning: statement has no effect [-Wunused-value]
   15 |    for(a;a<sum.size();a+=(a&-a))sum[a]+=b;
      |        ^
shoes.cpp:15:11: 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:8: 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:16: 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:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int i=1;i<=s.size();i++){
      |               ~^~~~~~~~~~

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