Submission #837458

#	Time	Username	Problem	Language	Result	Execution time	Memory
837458		abczz	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	118 ms	24652 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <vector>
#include <cstdlib>
#include <map>
#define ll long long
 
using namespace std;
 
ll n, f, x, y, st[800000], id[2][200000];
bool B[200000];
vector <ll> V[2][200000], X;
void build(ll id, ll l, ll r) {
	if (l == r) {
		st[id] = 1;
		return;
	}
	ll mid = (l+r)/2;
	build(id*2, l, mid);
	build(id*2+1, mid+1, r);
	st[id] = st[id*2] + st[id*2+1];
}
 
ll query(ll id, ll l, ll r, ll ql, ll qr) {
	if (qr < l || r < ql) return 0;
	else if (ql <= l && r <= qr) return st[id];
	ll mid = (l+r)/2;
	return query(id*2, l, mid, ql, qr) + query(id*2+1, mid+1, r, ql, qr);
}
 
void update(ll id, ll l, ll r, ll q) {
	if (l == r) {
		st[id] = 0;
		return;
	}
	ll mid = (l+r)/2;
	if (q <= mid) update(id*2, l, mid, q);
	else update(id*2+1, mid+1, r, q);
	st[id] = st[id*2] + st[id*2+1];
}
 
long long count_swaps(std::vector<int> s) {
  build(1, 0, s.size()-1);
	f = 0;
	for (int i=0; i<s.size(); ++i) {
		V[(s[i] < 0)][abs(s[i])-1].push_back(i);
	}
  for (int i=0; i<s.size(); ++i) {
    if (B[i]) continue;
    auto u = V[1][abs(s[i])-1][id[1][abs(s[i])-1]];
    auto v = V[0][abs(s[i])-1][id[0][abs(s[i])-1]];
    B[u] = B[v] = 1;
    ++id[0][abs(s[i])-1];
    ++id[1][abs(s[i])-1];
    f += query(1, 0, s.size()-1, 0, u)-1;
    update(1, 0, s.size()-1, u);
    f += query(1, 0, s.size()-1, 0, v)-1;
    update(1, 0, s.size()-1, v);
  }
	return f;
}

Compilation message (stderr)

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