Submission #318128

#	Time	Username	Problem	Language	Result	Execution time	Memory
318128		NicolaAbusaad2014	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	694 ms	49772 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long>tree;
long long mod=1e9+7;
long long power(long long x,long long p)
{
    if(p==0){
        return 1;
    }
    long long z=power(x,p/2);
    z=(z*z)%mod;
    if(p%2==1){
        z=(z*x)%mod;
    }
    return z;
}
long long power_of_two(long long x)
{
    long long z=0;
    while(x>1){
        x/=2;
        z++;
    }
    return z;
}
void segment_tree(vector<long long>v)
{
    long long x=v.size();
    x=power_of_two(x);
    x=power(2,x);
    if(v.size()!=x){
        x*=2;
    }
    tree.resize(x*2);
    tree[0]=x;
    for(long i=0;i<v.size();i++){
        tree[i+x]=v[i];
    }
    for(long i=x-1;i>0;i--){
        tree[i]=tree[i*2]+tree[(i*2)+1];
    }
}
long long seg(long long l,long long r)
{
    l+=tree[0];
    r+=tree[0];
    long long ans=0;
    while(l<=r){
        if(l%2==1){
            ans+=tree[l];
        }
        if(r%2==0){
            ans+=tree[r];
        }
        l++;
        l/=2;
        r--;
        r/=2;
    }
    return ans;
}
void update(long long x,long long z)
{
    x+=tree[0];
    tree[x]=z;
    x/=2;
    while(x>0){
        tree[x]=tree[x*2]+tree[(x*2)+1];
        x/=2;
    }
}
long long count_swaps(std::vector<int> s) {
    long long n=s.size();
    vector<long long>v(n);
    segment_tree(v);
    map<long,vector<long> >vis;
    map<long,long>z;
    map<long,bool>ok;
    long long ans=0,x;
    for(long i=0;i<n;i++){
        vis[s[i]].push_back(i);
    }
    for(long i=0;i<n;i++){
        if(ok[i]){
            ok[i]=false;
        }
        else{
            x=vis[-s[i]][z[abs(s[i])]];
            ans+=(x-i-1)-seg(i,x);
            if(s[i]>0){
                ans++;
            }
            z[abs(s[i])]++;
            update(x,1);
            ok[x]=true;
        }
    }
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'void segment_tree(std::vector<long long int>)':
shoes.cpp:32:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   32 |     if(v.size()!=x){
      |        ~~~~~~~~^~~
shoes.cpp:37:19: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(long i=0;i<v.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