Submission #166414

#	Time	Username	Problem	Language	Result	Execution time	Memory
166414		socho	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	307 ms	30424 KiB

shoes

#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;

struct node {

   long long s, e, m, val;
   node *l, *r;
   node (long long _s, long long _e) {
       s = _s;
       e = _e;
       m = (s + e)/2;
       val = 0;
       if (s == e) return;
       l = new node(s, m);
       r = new node(m+1, e);
   }

   void upd(long long p, long long v) {
       if (s == p && s== e) {
           val = v;
           return;
       }
       if (p <= m) {
           l->upd(p, v);
       }
       else {
           r->upd(p, v);
       }
       val = l->val + r->val; // transition
   }

   long long qry(long long qs, long long qe) {
       if (qs <= s && e <= qe) {
           return val;
       }
       else if (qs > e || s > qe) {
           return 0; // base case
       }
       else {
           return l->qry(qs, qe) + r->qry(qs, qe); // transition
       }
   }
   
} *root;

void init(long long N) {
   root = new node(0, N-1);
}

void update(long long P, long long V) {
   root->upd(P, V);
}

long long query(long long A, long long B) {
   return root->qry(A, B);
}

long long count_swaps(vector<int> arr) {
	
	long long sideswaps = 0;
	set<pair<long long, long long> > ope;
	vector<pair<long long, long long> > ind;
	
	for (long long i=0; i<arr.size(); i++) {
		long long num = arr[i];
		long long oth = -num;
		set<pair<long long, long long> >::iterator x = ope.lower_bound(make_pair(oth, LLONG_MIN));
		if (x != ope.end() && x->first == oth) {
			// pair<long long, long long> wi = *x;
			ope.erase(x);
			ind.push_back(make_pair(min(x->second, i), max(i, x->second)));
		}
		else {
			if (num > 0) sideswaps++;
			ope.insert(make_pair(num, i));
		}
	}
	
	sort(ind.begin(), ind.end());
	
	init(arr.size());
	
	long long sw = 0;
	
	for (long long i=0; i<ind.size(); i++) {
		long long a = ind[i].first, b = ind[i].second;
		long long x = b - a - 1;
		x -= query(a, b);
		update(a, 1);
		update(b, 1);
		sw += x;
	}
	
	return sideswaps + sw;
	
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (long long i=0; i<arr.size(); i++) {
                      ~^~~~~~~~~~~
shoes.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (long long i=0; i<ind.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