Submission #559373

#	Time	Username	Problem	Language	Result	Execution time	Memory
559373		LastRonin	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	109 ms	23760 KiB

shoes

//#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
 
const ll N = 2e5;
 
ll n;
vector<ll> st[N], ex[N];
bool was[N];
ll cur[N];

struct seg {
	ll t[4 * N] = {0};
	void upd(ll p, ll v = 1, ll tl = 1, ll tr = n) {
		if(tl == tr) {
			t[v] = 1;
			return;
		}
		ll m = (tl + tr) >> 1ll;
		if(p <= m)upd(p, v * 2, tl, m);
		else upd(p, v * 2 + 1, m + 1, tr);
		t[v] = t[v] + 1;
	}
	ll get(ll l, ll r, ll v = 1, ll tl = 1, ll tr = n) {
		if(l > tr || tl > r)return 0;
		if(l <= tl && tr <= r)return t[v];
		ll m = (tl + tr) >> 1ll;
		return get(l, r, v * 2, tl, m) + get(l, r, v * 2 + 1, m + 1, tr);
	}
} rt;
 
long long count_swaps(vector<int> s) {
	n = s.size();
	ll pos = 0;
	for(auto u : s) {
		if(u < 0) {
			st[-u].pb(pos++);
		}
		else {
			ex[u].pb(pos++);
		}
	}
	ll ans = 0;
	for(int j = 0; j < n; j++) {
		if(was[j])continue;
		ll z = -1;
		if(s[j] < 0) {
			ll z = ex[-s[j]][cur[-s[j]]];
			cur[-s[j]]++;
			ans += (z  - (j + 1)) - rt.get(j + 1, z);
			rt.upd(z, 1);
			was[z] = 1;
		}
		else {
			ll z = st[s[j]][cur[s[j]]];
			cur[s[j]]++;
			ans += (z - j) - rt.get(j, z);
			rt.upd(z, 1);
			was[z] = 1;
		}
	}
	return ans;
}
/*
int main() {
	int n;
	vector<int> s;
	cin >> n;
	for(int i = 0; i < n; i++) {
		s.pb(0);
		cin >> s.back();
	}
	cout << count_swaps(s);	
}
/**/

Compilation message (stderr)

shoes.cpp:77:1: warning: "/*" within comment [-Wcomment]
   77 | /**/
      |  
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:48:6: warning: unused variable 'z' [-Wunused-variable]
   48 |   ll z = -1;
      |      ^

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