Submission #759523

#	Time	Username	Problem	Language	Result	Execution time	Memory
759523		KN200711	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	61 ms	16412 KiB

shoes

#include "shoes.h"
# include <bits/stdc++.h>
# define ll long long
using namespace std;

const int MXN = 2e5;
vector<int> lf[100001], rg[100001];
int idx[2][100001];
int fen[200001], pl[200001];

void add(int a, int p) {
	while(a <= MXN) {
		fen[a] += p;
		a += a & (-a);
	}
	return;
}

int qry(int a) {
	int res = 0;
	while(a > 0) {
		res += fen[a];
		a -= a&(-a);
	}
	return res;
}

ll count_swaps(vector<int> s) {
	for(int i=1;i<=1e5;i++) {
		lf[i].clear();
		rg[i].clear();
		idx[0][i] = idx[1][i] = 0;
		fen[2 * i] = fen[2 * i - 1] = 0;
		pl[2 * i - 1] = pl[2 * i] = 0;
	}
	for(int i=0;i<s.size();i++) {
		add(i+1, 1);
		if(s[i] < 0) lf[-s[i]].push_back(i + 1);
		else rg[s[i]].push_back(i + 1);
	}
	
	int N = s.size();
	ll ans = 0ll;
	for(int i=1;i<=N;i++) {
		if(pl[i]) continue;
	//	cout<<i<<endl;
		int S = s[i - 1];
		if(S < 0) {
			// cari pasangannya
			int P = rg[-S][idx[1][-S]];
			pl[P] = 1;
			idx[1][-S]++;
			idx[0][-S]++;
			
			int ix = qry(P);
			ans += (1ll * ix - 1ll * 2);
			add(P, -1);
			add(i, -1);
		} else {
			int P = lf[S][idx[0][S]];
			pl[P] = 1;
			idx[0][S]++;
			idx[1][S]++;
			
			int ix = qry(P);
			ans += (1ll * ix - 1ll * 1);
			add(P, -1);
			add(i, -1);
		}
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  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