Submission #152513

#	Time	Username	Problem	Language	Result	Execution time	Memory
152513		MoNsTeR_CuBe	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	695 ms	44040 KiB

shoes

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

#define int long long
 
struct node{
	node* l, *r;
	int val;
	int lazy;
	
	void push(){
		if(l) l->lazy += lazy;
		if(r) r->lazy += lazy;
		val += lazy;
		lazy = 0;
	}
	
	void update(){
		val = l->val + r->val;
	}
};
 
void Build(node* root, int left, int right){
	if(left == right) return;
	int mid = (left+right)/2;
	
	root->l = new node{NULL,NULL,0,0};
	root->r = new node{NULL,NULL,0,0};
	
	Build(root->l, left, mid);
	Build(root->r, mid+1, right);
}
 
int query(node* root, int left, int right, int qL, int qR){
	root->push();
	if(left > qR || right < qL){
		return 0;
	}
	if(left >= qL && right <= qR){
		return root->val;
	}
	int mid = (left+right)/2;
	return query(root->l, left, mid, qL, qR) + query(root->r, mid+1, right, qL, qR);
}
 
void update(node* root, int left, int right, int qL, int qR, int x){
	root->push();
	if(left > qR || right < qL) return;
	if(left >= qL && right <= qR){
		root->lazy += x;
		root->push();
		return;
	}
	int mid = (left+right)/2;
	update(root->l, left, mid, qL, qR, x);
	update(root->r, mid+1, right, qL, qR, x);
	root->update();
}
#undef int
long long count_swaps(vector<int> s) {
#define int long long 
	int n = s.size();
	
	vector< bool > used(n, false);
	map< int, vector< int > > mape;
	
	node* root = new node{NULL,NULL,0,0};
	Build(root, 1, n+1);
	
	for(int i = n-1; i >= 0; i--){
		mape[s[i]].push_back(i);
		//cout << "PUSHED " << s[i] << ' ' << i << endl;
	}
	
	int ans = 0;
	
	for(int i = 0; i < n; i++){
		if(used[i]) continue;
		int index = mape[-s[i]].back();
		mape[-s[i]].pop_back();
		mape[s[i]].pop_back();
		
		used[i] = true;
		used[index] = true;
		
		//cout << "INDEXES " << i << ' ' << index << endl;
		
		int realI = i+query(root, 1, n+1, i+1,i+1);
		int realIndex = index+query(root, 1, n+1, index+1, index+1);
		
		//cout << "REAL " << realI << ' ' << realIndex << endl;
		
		update(root, 1, n+1, 1, index, 1);
		
		if(s[i] < 0){
			ans += abs(realI-realIndex)-1;
		}else{
			ans += abs(realI-realIndex);
		}
	}
	
	//cout << ans << endl;
	return ans;
}

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