Submission 828 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
828	15/05/2013 22:49:04	leandro	C - Aplanar	Accepted	2385	29.4 KiB	GNU G++ 5.1.0

Code

/*
    username: leandro
    program: Aplanar
    lang: C++
*/

#include <cstdio>
#define i64 long long

const int
      MaxN = 1000001;

struct node {
    int key;
	int own;
	i64 tot;
	int cnt;
	int hig;
	node* child[2];
	node() { }
	node(int key) :
	    key(key) {
		    own = 1;
			cnt = 1;
			hig = 0;
			tot = key;
			child[0] = NULL;
			child[1] = NULL;
		}
};
   
i64 sum;
node* aux;
node* root;
int N, K, i;
int A[MaxN];

inline int max(const int& a, const int& b) {
    return a > b ? a : b;
}

inline i64 hight(node* v) {
    return v != NULL ? v->hig : -1;
}

inline i64 total(node* v) {
    return v != NULL ? v->tot : 0;
}

inline i64 cant(node* v) {
    return v != NULL ? v->cnt : 0;
}

void update(node* v) {
    v->hig = max(hight(v->child[0]), hight(v->child[1])) + 1;
	v->cnt = cant(v->child[0]) + cant(v->child[1]) +  v->own;
	v->tot = (i64) v->key * v->own + total(v->child[0]) + total(v->child[1]);
}

node* rotate(node* rot, int c) {
    aux = rot->child[c];
	rot->child[c] = aux->child[1-c];
	aux->child[1-c] = rot;
	update(rot);
	update(aux);
	return aux;
}

node* insert(node* v, const int& val) {
    if (v == NULL)
	    return new node(val);
	if (v->key == val)
		v->own++;
	else {
	    int c = val > v->key;
		v->child[c] = insert(v->child[c], val);
		if (hight(v->child[c]) - hight(v->child[1-c]) == 2) {
		    if (c == 1) if (v->child[1]->key > val) v->child[1] = rotate(v->child[1], 0);
			if (c == 0) if (v->child[0]->key < val) v->child[0] = rotate(v->child[0], 1);
			v = rotate(v, c);
		}
	}
	update(v);
	return v;
}

node* erase(node* v, const int& val) {
    if (v->key == val)
	    v->own--;
	else {
	    int c = val > v->key;
		v->child[c] = erase(v->child[c], val);
	}
	update(v);
	return v;
}

i64 solve(int median) {
    aux = root;
	i64 cnt = 0;
	i64 tot = 0;
	for (;;) {
	    if (aux->key >= median) {
		    cnt += aux->own +  cant(aux->child[1]);
			tot += aux->tot - total(aux->child[0]);
			if (aux->key != median)
			     aux = aux->child[0];
			else break;
		} else aux = aux->child[1];
	}
	return (tot - median * cnt) + (median * (K - cnt) - (sum - tot));
}

i64 search(int kth = (K + 1) >> 1) {
    aux = root;
	for(;;) {
	    if (cant(aux->child[0]) < kth) {
		    if (cant(aux->child[0]) + aux->own < kth) {
			       kth -= cant(aux->child[0]) + aux->own;
				   aux = aux->child[1];
			} else break;
		} else aux = aux->child[0];
	}
	return solve(aux->key);
}

int main() {
	
	scanf("%d%d", &N, &K);
	for (i = 1; i <= N; i++)
	    scanf("%d", &A[i]);
	
	root = NULL;
	for (i = 1; i <  K; i++) {
	    sum  = sum + A[i];
		root = insert(root, A[i]);
	}
	
	i64 pos;
	i64 aux;
	i64 sol = 1LL << 60LL;
	
	for (i = K; i <= N; i++) {
	    sum  = sum + A[i];
	    root = insert(root, A[i]);
		aux = search();
		if (aux < sol) {
		    sol = aux;
			pos = i - K + 1;
		}
		sum  = sum - A[i - K + 1];
		root = erase(root, A[i - K + 1]);
	}
	
	printf("%lld\n%d\n", sol, pos);
	
    return 0;
	
}

Judgement Details

Case#0: [4460544 bytes] [0 ms] ok 2 tokens

Case#1: [4513792 bytes] [156 ms] ok 2 tokens

Case#2: [4509696 bytes] [392 ms] ok 2 tokens

Case#3: [21028864 bytes] [1176 ms] ok 2 tokens

Case#4: [5386240 bytes] [643 ms] ok 2 tokens

Case#5: [15020032 bytes] [972 ms] ok 2 tokens

Case#6: [26517504 bytes] [1914 ms] ok 2 tokens

Case#7: [4513792 bytes] [831 ms] ok 2 tokens

Case#8: [4460544 bytes] [439 ms] ok 2 tokens

Case#9: [30822400 bytes] [2385 ms] ok 2 tokens

Case#10: [30879744 bytes] [2071 ms] ok 2 tokens

Case#11: [4472832 bytes] [0 ms] ok 2 tokens

Case#12: [4509696 bytes] [0 ms] ok 2 tokens

Case#13: [4956160 bytes] [15 ms] ok 2 tokens

Case#14: [4743168 bytes] [15 ms] ok 2 tokens

Case#15: [5316608 bytes] [47 ms] ok 2 tokens

Case#16: [8429568 bytes] [203 ms] ok 2 tokens

Case#17: [4513792 bytes] [78 ms] ok 2 tokens

Case#18: [4456448 bytes] [15 ms] ok 2 tokens

Matcom Online Grader