Submission #470066

#	Time	Username	Problem	Language	Result	Execution time	Memory
470066		PiejanVDC	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	224 ms	140784 KiB

shoes

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

int st[(int)1e5 * 8];
vector<int>v;

void build(int p, int l, int r) {
	if(l == r) {
		st[p] = 1;
		return;
	}
	build(2*p,l,(l+r)/2);
	build(2*p+1,(l+r)/2+1,r);
	st[p] = r-l+1;
	return;
}

int l,r,up;

int sum(int p, int i, int j) {
	if(i <= r && i >= l && j <= r && j >= l) return st[p];
	if(i > r || j < l) return 0;
	return sum(2*p,i,(i+j)/2) + sum(2*p+1,(i+j)/2+1,j);
}

void upd(int p, int i, int j) {
	if(up <= j && up >= i) {
		st[p]--;
	} else return;
	if(i == j) return;
	upd(2*p,i,(i+j)/2);
	upd(2*p+1,(i+j)/2+1,j);
	return;
}

long long count_swaps(vector<int> s) {
	int c=0;
	int n = s.size();
	build(1,0,n-1);
	vector<queue<int>>pos((int)1e5+1),neg((int)1e5+1);
	for(int i = 0 ; i < n ; i++) {
		if(s[i] > 0) {
			pos[s[i]].push(i);
		} else neg[-s[i]].push(i);
	}
	vector<bool>seen(n+1,false);
	long long ans = 0;
	for(int i = 0 ; i < n-1 ; i++) {
		if(seen[i]) continue;
		int e;
		if(s[i] > 0) {
			e = neg[s[i]].front();
		} else e = pos[-s[i]].front();
		seen[e]=true;
		pos[abs(s[i])].pop();
		neg[abs(s[i])].pop();
		l = i, r = e;
		int cnt = sum(1,0,n-1);
		ans+=cnt-2;
		if(s[i] > 0) ans++;
		up = e;
		upd(1,0,n-1);
	}
	return ans;
}

/*signed main() {
	int n; cin >> n;
	vector<int>v(n);
	for(auto &z : v)
		cin >> z;
	cout << count_swaps(v);
}*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:38:6: warning: unused variable 'c' [-Wunused-variable]
   38 |  int c=0;
      |      ^

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