oj.uz

Submission #100273

# Submission time Handle Problem Language Result Execution time Memory
100273 2019-03-10T08:05:56 Z IvanC Simfonija (COCI19_simfonija) C++17
110 / 110
 139 ms 7416 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 6620 KB Output is correct
2 Correct 71 ms 6648 KB Output is correct
3 Correct 67 ms 6648 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6620 KB Output is correct
2 Correct 67 ms 6648 KB Output is correct
3 Correct 65 ms 6520 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6576 KB Output is correct
2 Correct 66 ms 6520 KB Output is correct
3 Correct 63 ms 6520 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 6596 KB Output is correct
2 Correct 96 ms 7320 KB Output is correct
3 Correct 139 ms 7248 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6652 KB Output is correct
2 Correct 112 ms 7416 KB Output is correct
3 Correct 123 ms 7300 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 6684 KB Output is correct
2 Correct 107 ms 7288 KB Output is correct
3 Correct 120 ms 7288 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 6632 KB Output is correct
2 Correct 99 ms 7336 KB Output is correct
3 Correct 81 ms 7348 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 6568 KB Output is correct
2 Correct 127 ms 7368 KB Output is correct
3 Correct 89 ms 7364 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 6560 KB Output is correct
2 Correct 63 ms 7288 KB Output is correct
3 Correct 94 ms 7276 KB Output is correct