Submission #67181

#	Time	Username	Problem	Language	Result	Execution time	Memory
67181		radoslav11	Bubble Sort 2 (JOI18_bubblesort2)	C++14	Compilation error	0 ms	0 KiB

bubblesort2

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

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

static int q, n;

random_device rd;
mt19937 mt(rd());

struct node
{
	int sz, prior, value, answer, lazy;
	pair<int, int> v;
	node *l, *r;

	node()
	{
		prior = value = sz = answer = lazy = 0;
		l = r = nullptr;
	}

	node(int vv, int x)
	{
		v = {vv, x};
		value = answer = x;
		l = r = nullptr;
		prior = mt();
		lazy = 0;
		sz = 1;
	}
};

using pnode = node*;

inline int size(pnode t) { return t ? t->sz : 0; }

void push(pnode &t)
{
	if(!t) return;
	if(!t->lazy) return;
	
	t->answer += t->lazy;
	t->value += t->lazy;

	if(t->l) t->l->lazy += t->lazy;
	if(t->r) t->r->lazy += t->lazy;

	t->lazy = 0;
}

void pull(pnode &t)
{
	if(!t) return;

	push(t->l);
	push(t->r);

	t->sz = 1 + size(t->l) + size(t->r);

	t->answer = t->value;
	if(t->l) chkmax(t->answer, t->l->answer);
	if(t->r) chkmax(t->answer, t->r->answer);
}

void merge(pnode &t, pnode l, pnode r)
{
	push(l), push(r);
	if(!l) { t = r; return; }
	if(!r) { t = l; return; }

	if(l->prior > r->prior)
		merge(l->r, l->r, r), t = l;
	else
		merge(r->l, l, r->l), t = r;

	pull(t);
}

void split(pnode t, pnode &l, pnode &r, pair<int, int> k)
{
	push(t);
	if(!t) { l = r = nullptr; return; }

	if(t->v <= k)
		split(t->r, t->r, r, k), l = t;
	else
		split(t->l, l, t->l, k), r = t;

	pull(t);
}

void split_sz(pnode t, pnode &l, pnode &r, int k, int add = 0)
{
	push(t);
	if(!t) { l = r = nullptr; return; }

	int idx = add + size(t->l);
	if(idx <= k)
		split_sz(t->r, t->r, r, k, idx + 1), l = t;
	else
		split_sz(t->l, l, t->l, k, add), r = t;

	pull(t);
}


pnode root;

std::vector<int> count_scans(std::vector<int> A, std::vector<int> X, std::vector<int> V)
{
	q = X.size();
	n = A.size();
	std::vector<int> answer(q);

	for(int i = 0; i < n; i++)
	{
		pnode l, r, nw = new node(A[i], i);
		
		split(root, l, r, {A[i], i});

		nw->value -= size(l);
		nw->answer -= size(l);
		if(r) r->lazy--;

		merge(root, l, nw);
		merge(root, root, r);
	}

	for(int i = 0; i < q; i++)
	{
		int x = X[i], v = V[i];
		
		pnode l, r, mid;
	
		split(root, l, r, {A[x], x - 1});
		split_sz(r, mid, r, 0);
		
		if(r) r->lazy += 1;
		
		merge(root, l, r);
	
		split(root, l, r, {v, x});
		mid->v = {v, x};
		
		mid->value = mid->answer = x - size(l);
		
		if(r) r->lazy -= 1;

		merge(root, l, mid);
		merge(root, root, r);

		answer[i] = root->answer;
	
		A[x] = v;
	}

	return answer;
}

Compilation message (stderr)

/tmp/ccToELNO.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