제출 #1047339

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

shoes

#include "shoes.h"

#include <bits/stdc++.h>
using namespace std;

const int lim=2e5+100;

struct{
	int tree[lim];
	void update(int p,int val){
		p++;
		while(p<lim){
			tree[p]+=val;
			p+=p&-p;
		}
	}
	int query(int p){
		p++;
		int ans=0;
		while(p){
			ans+=tree[p];
			p-=p&-p;
		}
		return ans;
	}
	int query(int l,int r){
		if(r<l)return 0;
		return query(r)-query(l-1);
	}
}fw;

long long count_swaps(std::vector<int> s) {
	int ans=0;
	int n=s.size();
	int p1[n]{},p2[n]{};
	vector<int>left[n],right[n];
	for(int i=0;i<n;i++){
		if(s[i]<0){
			if(p1[-s[i]]<right[-s[i]].size()){
				int ind=right[-s[i]][p1[-s[i]]];
				p1[-s[i]]++;
				int k=fw.query(ind+1,i);
				ans+=k+i-ind;
				fw.update(i+1,-1);
				fw.update(ind,1);
			}else{
				left[-s[i]].push_back(i);
			}
		}else{
			if(p2[s[i]]<left[s[i]].size()){
				int ind=left[s[i]][p2[s[i]]];
				p2[s[i]]++;
				int k=fw.query(ind+1,i);
				ans+=k+i-ind-1;
				fw.update(i+1,-1);
				fw.update(ind+1,1);
			}else{
				right[s[i]].push_back(i);
			}
		}
		//cerr<<ans<<"\n";
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    if(p1[-s[i]]<right[-s[i]].size()){
      |       ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
shoes.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    if(p2[s[i]]<left[s[i]].size()){
      |       ~~~~~~~~^~~~~~~~~~~~~~~~~~

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