답안 #43959

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43959 2018-03-29T00:01:04 Z IvanC Kralj (COCI16_kralj) C++17
56 / 140
1831 ms 131072 KB
#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

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);
   ~~~~~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1207 ms 34296 KB Output is correct
2 Correct 829 ms 41680 KB Output is correct
3 Correct 1093 ms 57392 KB Output is correct
4 Correct 1010 ms 67984 KB Output is correct
5 Incorrect 1620 ms 76988 KB Output isn't correct
6 Incorrect 1149 ms 87800 KB Output isn't correct
7 Incorrect 1732 ms 101548 KB Output isn't correct
8 Incorrect 1301 ms 109292 KB Output isn't correct
9 Incorrect 1831 ms 127048 KB Output isn't correct
10 Incorrect 1610 ms 131072 KB Output isn't correct