Submission #67720

#	Time	Username	Problem	Language	Result	Execution time	Memory
67720		chpipis	Bubble Sort 2 (JOI18_bubblesort2)	C++11	Compilation error	0 ms	0 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> ii;

struct node {
	node *left, *right;
	ii key;
	int val, mx, sz;
	int prior, lazy;

	node(ii k, int v) {
		left = right = NULL;
		key = k;
		val = mx = v;
		sz = 1;
		prior = rand();
		lazy = 0;
	}
};

typedef node* pnode;

void push(pnode t) {
	if (!t || t->lazy == 0)
		return;
	t->val += t->lazy;
	t->mx += t->lazy;
	if (t->left)
		t->left->lazy += t->lazy;
	if (t->right)
		t->right->lazy += t->lazy;
	t->lazy = 0;
}

void update(pnode t) {
	if (!t) return;
	push(t->left);
	push(t->right);
	t->mx = t->val;
	t->sz = 1;
	if (t->left) {
		t->mx = max(t->mx, t->left->mx);
		t->sz += t->left->sz;
	}
	if (t->right) {
		t->mx = max(t->mx, t->right->mx);
		t->sz += t->right->sz;
	}
}

void split(pnode t, pnode &L, pnode &R, ii k) {
	if (!t) {
		L = R = NULL;
		return;
	}
	push(t);
	if (k < t->key) {
		split(t->left, L, t->left, k);
		R = t;
	} else {
		split(t->right, t->right, R, k);
		L = t;
	}
	update(t);
}

void merge(pnode &t, pnode L, pnode R) {
	push(L); push(R);
	if (!L || !R) {
		t = (L ? L : R);
		return;
	}
	if (L->prior > R->prior) {
		merge(L->right, L->right, R);
		t = L;
	} else {
		merge(R->left, L, R->left);
		t = R;
	}
	update(t);
}

void inorder(pnode t) {
	if (!t) return;
	push(t);
	update(t);
	inorder(t->left);
	printf("(%d, %d): val = %d, mx = %d\n", t->key.fi, t->key.se, t->val, t->mx);
	inorder(t->right);
}

vector<int> count_scans(vector<int> A, vector<int> X, vector<int> V) {
	srand(time(NULL));
	vector<ii> sor;
	int n = (int)A.size();
	for (int i = 0; i < n; i++) {
		sor.pb(mp(A[i], i));
	}
	sort(sor.begin(), sor.end());
	pnode root = NULL;
	for (int i = 0; i < n; i++) {
		merge(root, root, new node(sor[i], sor[i].se - i));
	}
	vector<int> ans;
	int q = (int)X.size();
	for (int i = 0; i < q; i++) {
		ii bef = mp(A[X[i]], X[i]);
		A[X[i]] = V[i];
		ii aft = mp(A[X[i]], X[i]);
		pnode other = NULL, dummy = NULL;
		split(root, root, other, bef);
		if (other) {
			other->lazy++;
			push(other);
		}
		split(root, root, dummy, mp(bef.fi, bef.se - 1));
		delete dummy;
		merge(root, root, other);
		split(root, root, other, aft);
		merge(root, root, new node(aft, X[i] - (root ? root->sz : 0)));
		if (other) {
			other->lazy--;
			push(other);
		}
		merge(root, root, other);
		//puts("NOW INORDER");inorder(root);
		ans.pb(root->mx);
	}
	return ans;
}

Compilation message (stderr)

/tmp/cc08HIv3.o: In function `main':
grader.cpp:(.text.startup+0x12b): undefined reference to `countScans(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status