Submission #26719

#	Time	Username	Problem	Language	Result	Execution time	Memory
26719		model_code	Untitled (POI11_rot)	C++11	100 / 100	399 ms	26824 KiB

Main

/*************************************************************************
 *                                                                       *
 *                    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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10