Submission #26719

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26719	2017-07-05T10:22:42 Z	model_code	Tree Rotations (POI11_rot)	C++11	100 / 100	399 ms	26824 KB

/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Rotacje na drzewie                               *
 *   Autor:             Adam Karczmarz                                   *
 *   Opis:              Rozwiazanie wzorcowe                             *
 *   Zlozonosc czasowa: O(n*lg^2(n))                                     *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>

#define REP(AA,BB) for(AA=0; AA<(BB); ++AA)
#define FOR(AA,BB,CC) for(AA=BB; AA<(CC); ++AA)
#define FC(AA,BB) for(typeof(AA.begin()) BB=AA.begin(); BB!=AA.end(); ++BB)

using namespace std;

// wezel drzewa 
struct node;
struct node {
	node *left, *right, *prev;
	int sz, mn; long long inv; 
	node() { left=right=prev=0; inv=0LL; }
};

node *p[200100]; int cur, cnt[200100], MX, f;

// drzewo potegowe
int get(int x) {
	int res=0;
	while(x>0) {
		res+=cnt[x];
		x-=x&(-x);
	}
	return res;
}

void ins(int x, int v) {
	while(x<=MX) {
		cnt[x]+=v;
		x+=x&(-x);
	}
}

// wczytywanie wejscia
void read_input(node *tr) {
	int c; f=scanf("%d", &c);
	if(c!=0) {
		tr->sz=1;
		tr->mn=++cur;
		p[c-1]=tr;
	}
	else {
		tr->left=new node; tr->right=new node;
		read_input(tr->left); read_input(tr->right);
		tr->mn=tr->left->mn;
		tr->sz=tr->left->sz+tr->right->sz;
	}
}

// wstepne rotacje i liczenie dla kazdego wezla "prawego" poprzednika na sciezce do korzenia
void prepare(node *tr, node *par, int x) {
	if(par!=0) {
		if(x)
			tr->prev=par;
		else
			tr->prev=par->prev;
	}
	if(tr->sz==1)
		return;
	if(tr->right->sz>tr->left->sz)
		swap(tr->left, tr->right);
	prepare(tr->left, tr, 0); prepare(tr->right, tr, 1);
}

// obliczanie wyniku przy znanej liczbie inwersji w kazdym wezle
long long compute(node *tr) {
	if(tr->sz==1)
		return 0LL;
	return min(tr->inv, (long long)(tr->left->sz)*(tr->right->sz)-tr->inv)+compute(tr->left)+compute(tr->right);
}

int main(void) {
	int n, i; node *root=new node, *tmp;
	f=scanf("%d", &n); MX=n;
	read_input(root); prepare(root, 0, 0);
	FOR(i,1,n+1)
		ins(i,1);
	REP(i,n) {
		tmp=p[i]->prev;
		// aktualizacja "prawych" poprzednikow na sciezce do korzenia
		while(tmp!=0) {
			tmp->inv+=get(tmp->left->mn+tmp->left->sz-1)-get(tmp->left->mn-1);
			tmp=tmp->prev;
		}
		ins(p[i]->mn, -1);
	}
	printf("%lld\n", compute(root));
	return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	3516 KB	Output is correct
2	Correct	3516 KB	Output is correct
3	Correct	3516 KB	Output is correct
4	Correct	3516 KB	Output is correct
5	Correct	3516 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	3516 KB	Output is correct
2	Correct	3516 KB	Output is correct
3	Correct	3516 KB	Output is correct
4	Correct	3516 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	3648 KB	Output is correct
2	Correct	3648 KB	Output is correct
3	Correct	3648 KB	Output is correct
4	Correct	3648 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3928 KB	Output is correct
2	Correct	0 ms	3912 KB	Output is correct
3	Correct	3 ms	3928 KB	Output is correct
4	Correct	0 ms	3960 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4964 KB	Output is correct
2	Correct	6 ms	4704 KB	Output is correct
3	Correct	29 ms	6420 KB	Output is correct
4	Correct	6 ms	4924 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	8268 KB	Output is correct
2	Correct	29 ms	8812 KB	Output is correct
3	Correct	53 ms	9984 KB	Output is correct
4	Correct	53 ms	10260 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	14764 KB	Output is correct
2	Correct	73 ms	13380 KB	Output is correct
3	Correct	113 ms	12196 KB	Output is correct
4	Correct	69 ms	11900 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	176 ms	14888 KB	Output is correct
2	Correct	143 ms	15332 KB	Output is correct
3	Correct	133 ms	17480 KB	Output is correct
4	Correct	53 ms	17212 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	176 ms	21420 KB	Output is correct
2	Correct	126 ms	20772 KB	Output is correct
3	Correct	189 ms	20600 KB	Output is correct
4	Correct	203 ms	20548 KB	Output is correct
5	Correct	293 ms	19488 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	213 ms	22060 KB	Output is correct
2	Correct	139 ms	25476 KB	Output is correct
3	Correct	149 ms	24088 KB	Output is correct
4	Correct	109 ms	26120 KB	Output is correct
5	Correct	223 ms	21732 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	239 ms	22720 KB	Output is correct
2	Correct	183 ms	23332 KB	Output is correct
3	Correct	176 ms	22260 KB	Output is correct
4	Correct	256 ms	22724 KB	Output is correct
5	Correct	243 ms	26824 KB	Output is correct
6	Correct	399 ms	22260 KB	Output is correct

Submission #26719

Compilation message