Submission #43959

#	Time	Username	Problem	Language	Result	Execution time	Memory
43959		IvanC	Kralj (COCI16_kralj)	C++17	56 / 140	1831 ms	131072 KiB

kralj

#include <bits/stdc++.h>
#define LSOne(S) (S & (-S))
using namespace std;
const int MAXN = 1e6 + 10;
int Dwarves[MAXN],A[MAXN],N,bit[MAXN],exibe;
multiset<int> Elves;
void update(int idx,int delta){
	//printf("Update comeca\n");
	while(idx < MAXN){
		//printf("Idx %d\n",idx);
		bit[idx] += delta;
		idx += LSOne(idx);
	}
	//printf("Terminou Update\n");
}
int read(int idx){
	//printf("Read comecou\n");
	int ans = 0;
	while(idx > 0){
		ans += bit[idx];
		idx -= LSOne(idx);
	}
	//printf("Terminou Read\n");
	return ans;
}
int busca(int ai){
	//printf("Comecou BS\n");
	int desconto = read(ai-1);
	int ini = 1,fim = 2*N,meio,resp = -1;
	while(ini <= fim){
		meio = (ini+fim)/2;
		if(read(meio) - desconto > 0){
			resp = meio;
			fim = meio - 1;
		}
		else{
			ini = meio + 1;
		}
	}
	//printf("Terminou BS %d\n",resp);
	if(resp > N) resp -= N;
	return resp;
}
int main(){
	scanf("%d",&N);
	for(int i = 1;i<=N;i++){
		scanf("%d",&A[i]);
		update(i,1);
		update(i+N,1);
	}
	for(int i = 1;i<=N;i++){
		scanf("%d",&Dwarves[i]);
	}
	for(int i = 1;i<=N;i++){
		int x;
		scanf("%d",&x);
		Elves.insert(x);
	}
	for(int vez = 1;vez<=N;vez++){
		int posicao = busca(A[vez]);
		int dwarf = Dwarves[posicao];
		update(posicao,-1);
		update(posicao+N,-1);
		if((*Elves.rbegin()) < dwarf){
			Elves.erase(Elves.begin());
		}
		else{
			exibe++;
			Elves.erase(Elves.lower_bound(dwarf));
		}
		//printf("Vez %d\n",vez);
	}
	printf("%d\n",exibe);
	return 0;
}

Compilation message (stderr)

kralj.cpp: In function 'int main()':
kralj.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
kralj.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&A[i]);
   ~~~~~^~~~~~~~~~~~
kralj.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&Dwarves[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~
kralj.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~

• Subtask 1: 56 / 140