제출 #1021210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021210		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	76 ms	18628 KiB

shoes

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

long long st[800001],v[800001];
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];
    }
}

long long 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;
}

컴파일 시 표준 에러 (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: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15