Submission #591006

#	Time	Username	Problem	Language	Result	Execution time	Memory
591006		almothana05	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	469 ms	29112 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
map<int , vector<int> >num;
vector<pair<int , int> >erg;
int vis[200000] , pref[200000], seg[800000], lazy[800000];
void pro(int id , int l , int r){
	seg[id] += lazy[id];
	if(l != r){
		lazy[id * 2] += lazy[id];
		lazy[id * 2 + 1] += lazy[id];
	}
	lazy[id] = 0;
}
int up(int id , int l , int r, int gewl , int gewr , int gew){
	if(gewr < gewl){
		return 0;
	}
	pro(id , l , r);
	if(l > gewr || gewl > r){
		return 0;
	}
	else if(gewl <= l && r <= gewr){
		// cout << l << ' ' << r <<' ' << id <<  "\n";
		seg[id] += gew;

		if(l != r){
			lazy[id * 2] += gew;
			lazy[id * 2 + 1] += gew;
		}
		return gew;
	}
	int m = (l + r)/2 , cmp;
	cmp = up(id * 2 , l , m , gewl , gewr , gew) | up(id * 2 + 1 , m + 1 , r , gewl , gewr , gew);
	seg[id] += cmp;
	return cmp;
}
long long count_swaps(vector<int> s) {
	long long menge = s.size() , be , en , re = 0 , len;
	for(len = 1 ; len < menge ; len *= 2);
	for(int i = menge - 1 ; i >= 0 ; i--){
		num[s[i]].push_back(i);
	}
	for(int i = 0 ; i < menge ; i++){
		if(vis[i] == 1){
			continue;
		}
		be = i;
		en = num[s[i] * -1][num[s[i] * -1].size() - 1];
		num[s[i] * -1].pop_back();
		num[s[i]].pop_back();
		// if(be > en){
		// 	swap(be , en);
		// }
		up(1 , 1 , len , be + 2 , en  , 1);
		up(1 , 1 , len , be + 1 , be + 1 , 0);
		up(1 , 1 , len , en + 1 , en + 1, 0);
		vis[be] = 1;
		vis[en] = 1;
		// cout << be << ' ' << en << "\n\n";
		be += seg[be + len];
		en += seg[en + len];
		// cout << be << ' ' << en << "\n\n";
		if(s[i] > 0){
			re++;
		}
		re += (en - be - 1);
	}

	return re;
}

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