Submission #767072

#	Time	Username	Problem	Language	Result	Execution time	Memory
767072		Ludissey	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	436 ms	167584 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <bitset>
#include <tuple>
#include <cmath>
#include <cstdint>
#include <stack>
#include <cassert>
#include <cstdio>
#include <queue>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <sstream> 

#define INF  9223372036854775801
#define int long long
#define double long double

#define MOD(a) ((a) % 1000000007  + 1000000007 ) % 1000000007
#define F first
#define caseOut(t) cout << "Case " << t << ": "; 
#define S second
#define USACO_SETUP() ifstream cin("paint.in"); ofstream cout("paint.out");
#define SETUP() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

struct node {
	node* left, * right;
	int sum;
	int lazy = 0;
	void update() {
		sum = left->sum + right->sum;
	}
};

void propagate(node *root, int left, int right) {
	if (root->lazy != 0) {
		root->sum += (left - right + 1) * root->lazy;
		if (left != right) {
			root->left->lazy += root->lazy;
			root->right->lazy += root->lazy;
		}
	}
	root->lazy = 0;
}

int query(node* root, int x, int left, int right) {
	propagate(root, left, right);
	if (left == right) return root->sum;
	if (x > right || x < left) return 0;
	int mid = (left+right)/2;
	if (x <= mid) return query(root->left, x, left, mid);
	else return query(root->right, x, mid + 1, right);
}

void update(node* root, int x, int uLeft, int uRight, int left, int right) {
	propagate(root, left, right);

	if (right<uLeft || left>uRight) return;
	if (right <= uRight && left >= uLeft) {
		root->lazy = x;
		propagate(root, left, right);
		return;
	}
	int mid = (left + right) / 2;
	update(root->left, x, uLeft, uRight, left, mid);
	update(root->right, x, uLeft, uRight, mid+1, right);
	root->update();
}

void build(node* root, int left, int right) {
	if (left == right) {
		root->sum = 0;
		return;
	}
	int mid = (left + right) / 2;

	root->left = new node{ NULL, NULL, 0 };
	root->right = new node{ NULL, NULL, 0 };

	build(root->left, left, mid);
	build(root->right, mid + 1, right);

	root->sum=0;
}

long long count_swaps(std::vector<signed> s) {
	int n = s.size();
	vector<int> prefx(n);
	vector<bool> uncount(n);
	int i = 0;
	node* root = new node{ NULL, NULL, 0 };
	build(root, 0, n-1);
	map<int, queue<int>> mp;
	int sum = 0;
	for (int i = 0; i < n; i++) mp[s[i]].push(i);
	for (auto u : mp)
	{
		while (!u.second.empty()) {

			int a = u.second.front();
			int b=mp[-u.first].front();
			if (b < a) swap(a, b);
			u.second.pop();
			mp[-u.first].pop();
			prefx[a] = b;
			prefx[b] = a;
			uncount[b] = true;

		}
	}
	for (int i = 0; i < n; i++)
	{
		if (uncount[i]) continue;
		int a = i;
		int b = prefx[a];
		int posA = query(root, a, 0, n - 1)+a;
		int posB= query(root, b, 0, n - 1)+b;
		int dist = (s[a] < 0) ? (posB - posA - 1) : (posB - posA);
		sum += dist;
		if (b - a > 1) update(root, 1, a + 1, b - 1, 0, n - 1);
	}
	return sum;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:99:6: warning: unused variable 'i' [-Wunused-variable]
   99 |  int i = 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