Submission #712969

#	Time	Username	Problem	Language	Result	Execution time	Memory
712969		mseebacher	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	2 ms	2652 KiB

shoes

//#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <functional>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#define mp make_pair
#define f first
#define s second
#define pb push_back

typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const lld pi = 3.14159265358979323846;



#define MAXI (int)1e5
#define LSOne(S) ((S) & -(S))
#define MSB(S) __builtin_clz(S)
vector<int> ad[MAXI];


 
vector<ll> ft;

ll sumFT(int index){
	ll sum = 0;
	while(index > 0){	
		sum+= ft[index];
		index -= LSOne(index);
	}
	return sum;
}
 
int getval(int index){
	int x = sumFT(index)-sumFT(index-1);
	if(x == 0) return 1; else return -1;
}
 
void updateFT(int index, ll val){
	while(index < (int)ft.size()){
		ft[index] += val;
		index += LSOne(index);
	}
}
 
void buildFT(vector<ll> a){
	for(int i = 1;i<(int)ft.size();i++){
		ft[i]+= a[i];
		int x = LSOne(i)+i;
		if(x < (int)ft.size())
			ft[x] += ft[i];
	}
	
}
 
void range_update(int l,int r,ll val){
	++r;
	if(r < (int)ft.size())
		updateFT(r,-val);
	updateFT(l,val);
	
}

long long count_swaps(vector<int> a){

	int n = a.size();
	vector<set<int>> left(2*n+1);
	vector<set<int>> right(2*n+1);
	
	vector<bool> marked(2*n,0);
	ll ans = 0;
	for(int i = 0;i<n;i++){
		if(a[i] < 0){
			int x = a[i]*-1;
			left[x].insert(i);
		}else right[a[i]].insert(i);
	}
	ft.assign(n+1,1);
	int links,rechts;
	for(int i = 0;i<n;i++){
		if(marked[i]) continue;
		if(a[i] < 0) {
			rechts = *right[abs(a[i])].begin();
		}else{
			ans++;
			rechts = *left[a[i]].begin();
		}
		right[abs(a[i])].erase(*right[abs(a[i])].begin());
		left[abs(a[i])].erase(*left[abs(a[i])].begin());
		links = i;
		
		ans += sumFT(rechts)-sumFT(links);
		updateFT(links,0);
		updateFT(rechts,0);
		marked[i] = 1;
		marked[rechts] = 1;
	}
	
	
	return ans;
}

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