Submission #1063601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063601		aaaaaarroz	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	348 ms	149588 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
template<class T, T m_(T, T)> struct IterativeSegmentTree{
	int n; vector<T> ST;
	IterativeSegmentTree(){}
	IterativeSegmentTree(vector<T> &a){
	n = a.size(); ST.resize(n << 1);
	for (int i=n;i<(n<<1);i++)ST[i]=a[i-n];
	for (int i=n-1;i>0;i--)ST[i]=m_(ST[i<<1],ST[i<<1|1]);
	}
	void update(int pos, T val){ // replace with val
	ST[pos += n] += val;
	for (pos >>= 1; pos > 0; pos >>= 1)
		ST[pos] = m_(ST[pos<<1], ST[pos<<1|1]);
	}
	T query(int l, int r){ // [l, r]
	T ansL, ansR; bool hasL = 0, hasR = 0;
	for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1) 
		ansL=(hasL?m_(ansL,ST[l++]):ST[l++]),hasL=1;
		if (r & 1) 
		ansR=(hasR?m_(ST[--r],ansR):ST[--r]),hasR=1;
	}
	if (!hasL) return ansR; if (!hasR) return ansL;
	return m_(ansL, ansR);
	}
};
int merge(int a, int b){
	return a+b;
}
long long count_swaps(vector<int> v) {
	int n=v.size();
	vector<int>vacio(n,0);
	IterativeSegmentTree<int,merge>st(vacio);
	long long cnt=0;
	map<int,queue<int>>pos;
	for(int i=0;i<n;i++){
		int zapato=v[i];
		if(!pos[-zapato].empty()){
			int mn_p=pos[-zapato].front();
			int mx_p=i;
			st.update(mn_p+1,1);
			st.update(mx_p,-1);
			int der=mx_p;
			int izq=mn_p+st.query(0,mn_p);
			bool menor=(v[i]>0);
			pos[-zapato].pop();
			cnt+=(der-izq-menor);
		}
		else{
			pos[zapato].push(i);
		}
	}
	return cnt;
}

Compilation message (stderr)

shoes.cpp: In member function 'T IterativeSegmentTree<T, m_>::query(int, int)':
shoes.cpp:24:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   24 |  if (!hasL) return ansR; if (!hasR) return ansL;
      |  ^~
shoes.cpp:24:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |  if (!hasL) return ansR; if (!hasR) return ansL;
      |                          ^~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:45:32: warning: 'ansR' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |    int izq=mn_p+st.query(0,mn_p);
      |                                ^

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