Submission #100273

#	Time	Username	Problem	Language	Result	Execution time	Memory
100273		IvanC	Simfonija (COCI19_simfonija)	C++17	110 / 110	139 ms	7416 KiB

simfonija

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef struct node* pnode;

const ll INF = 1e18;
const int MAXN = 1e5 + 10;

struct node{

	pnode l, r;
	ii key;
	int prior, size;
	ll sum;

	node(ii _key){
		key = _key;
		prior = rand();
		l = r = NULL;
		size = 1;
		sum = key.first;
	}

};

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

ll sm(pnode t){return t ? t->sum : 0;}

void upd(pnode t){

	if(!t) return; 

	t->size = sz(t->l) + 1 + sz(t->r);
	t->sum = sm(t->l) + t->key.first + sm(t->r);

}

void split(pnode t, pnode &l, pnode &r, ii key){

	if(!t){
		l = r = NULL;
		return;
	} 

	if(key < t->key){
		split(t->l, l, t->l, key);
		r = t;
	}
	else{
		split(t->r, t->r, r, key);
		l = t;
	}

	upd(t);

}

void merge(pnode &t,pnode l,pnode r){
	
	if(l == NULL){
		t = r;
	}
	else if(r == NULL){
		t = l;
	}
	else if(l->prior > r->prior){
		merge(l->r,l->r,r);
		t = l;
	}
	else{
		merge(r->l,l,r->l);
		t = r;
	}
	
	upd(t);

}

void insert(pnode &t, ii key){

	//printf("Oi 1\n");
	pnode aux = new node(key);
	pnode l, r;

	//printf("Oi 2\n");
	split(t, l, r, key);
	//printf("Oi 3\n");
	merge(t, l, aux);
	//printf("Oi 4\n");
	merge(t, t, r);

}

void remove(pnode &t, ii key){

	pnode l, mid, r;

	split(t, l, r, ii(key.first, key.second - 1));
	split(r, mid, r, key);

	merge(t, l, r);

}

ii kth(pnode t, int k){

	if(t == NULL) return ii(INF, INF);

	if(sz(t->l) + 1 == k) return t->key;

	if(k <= sz(t->l)) return kth(t->l, k);

	return kth(t->r, k - sz(t->l) - 1);

}

ll doQuery(pnode t){

	ii mediana = kth(t, (sz(t)+1)/2);
	ll xm = mediana.first;

	pnode l, r;
	split(t, l, r, mediana);

	ll tot1 = sz(l)*xm - sm(l);
	ll tot2 = sm(r) - sz(r)*xm;

	merge(t, l, r);

	return tot1 + tot2;

}

int A[MAXN], B[MAXN], K, N;
ii C[MAXN];

int main(){

	ll best = INF;
	scanf("%d %d",&N,&K);

	if(K == N){
		printf("0\n");
		return 0;
	}

	for(int i = 1;i<=N;i++){
		scanf("%d", &A[i]);
	}
	for(int i = 1;i <= N;i++){
		scanf("%d", &B[i]);
		C[i] = ii(A[i] - B[i], i);
	}

	sort(C+1, C+N+1);

	pnode raiz = NULL;
	int L = N - K;
	for(int i = 1;i <= L;i++){
		//printf("Add i %d\n",i);
		insert(raiz, C[i]);
	}
	best = min(best, doQuery(raiz));

	for(int i = L + 1;i<=N;i++){
		
		insert(raiz, C[i]);
		remove(raiz, C[i-L]);

		best = min(best, doQuery(raiz));

	}

	printf("%lld\n",best);

	return 0;

}

Compilation message (stderr)

simfonija.cpp: In function 'int main()':
simfonija.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&K);
  ~~~~~^~~~~~~~~~~~~~~
simfonija.cpp:151:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
   ~~~~~^~~~~~~~~~~~~
simfonija.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &B[i]);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11