Submission #1021192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021192		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	2 ms	4956 KiB

shoes

#include "shoes.h"
#include<iostream>
#include<vector>
using namespace std;

int st[400001],v[400001];
vector<int>sh[100001],sq[100001];

void bld(int nd,int l,int r){
    if(l==r)st[nd]=1,v[l]=1;
    else{
        int m=(l+r)/2;
        bld(nd*2,l,m);
        bld(nd*2+1,m+1,r);
        st[nd]=st[nd*2]+st[nd*2+1];
    }
}

int val(int nd,int l,int r,int p,int q){
    if(r<p||q<l)return 0;
    if(p<=l&&r<=q)return st[nd];
    int m=(l+r)/2;
    return val(nd*2,l,m,p,q)+val(nd*2+1,m+1,r,p,q);
}

void upd(int nd,int l,int r,int p){
    if(p<l||r<p)return;
    if(l==r)st[nd]=0,v[l]=0;
    else{
        int m=(l+r)/2;
        upd(nd*2,l,m,p);
        upd(nd*2+1,m+1,r,p);
        st[nd]=st[nd*2]+st[nd]*2+1;
    }
}

long long count_swaps(vector<int>s){
    long long r=0;
    bld(1,0,s.size()-1);
    for(int i=0;i<s.size();i++){
        if(s[i]<0)sq[-s[i]].push_back(i);
        else sh[s[i]].push_back(i);
    }
    for(int i=s.size()-1;0<=i;i--){
        if(v[i]){
            if(s[i]<0){
                r+=val(1,0,s.size()-1,sh[-s[i]].back(),i-1);
                upd(1,0,s.size()-1,sh[-s[i]].back());
                sh[-s[i]].pop_back();
                sq[-s[i]].pop_back();
            }else{
                r+=val(1,0,s.size()-1,sq[s[i]].back(),i-1)-1;
                upd(1,0,s.size()-1,sq[s[i]].back());
                sh[s[i]].pop_back();
                sq[s[i]].pop_back();
            }
        }
    }
	return r;
}

Compilation message (stderr)

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

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