Submission #36589

#	Time	Username	Problem	Language	Result	Execution time	Memory
36589		IvanC	역사적 조사 (JOI14_historical)	C++14	100 / 100	1879 ms	133784 KiB

historic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
const int BUCKET = 327;
vector<int> ida,volta;
int freq[BUCKET][MAXN],tempfreq[MAXN],versao[MAXN],divisao[MAXN],vetor[MAXN],iteracao,N,Q;
ll precalc[BUCKET][BUCKET];
void build(int id){
	for(int i = 0;i<min((id+1)*BUCKET,N);i++){
		int j = vetor[i];
		freq[id][j]++;
	}
	memset(tempfreq,0,sizeof(tempfreq));
	ll best = 0;
	for(int i = id*BUCKET;i<N;i++){
		int j = vetor[i];
		tempfreq[j]++;
		best = max(best, 1LL*tempfreq[j]*volta[j] );
		precalc[id][divisao[i]] = best;	
	}
}
int main(){
	scanf("%d %d",&N,&Q);
	for(int i = 0;i<N;i++){
		scanf("%d",&vetor[i]);
		divisao[i] = i/BUCKET;
		ida.push_back(vetor[i]);
	}
	sort(ida.begin(),ida.end());
	ida.erase(unique(ida.begin(),ida.end()),ida.end());
	for(int i = 0;i<ida.size();i++) volta.push_back(ida[i]);
	for(int i = 0;i<N;i++){
		vetor[i] = lower_bound(ida.begin(),ida.end(),vetor[i]) - ida.begin();
	}
	int tot_baldes = (N-1)/BUCKET;
	for(int i = 0;i<=tot_baldes;i++){
		build(i);
	}
	for(int q = 1;q<=Q;q++){
		int l,r;
		scanf("%d %d",&l,&r);
		l--;r--;
		ll resp = 0;
		iteracao++;
		int l_bucket = divisao[l];
		int r_bucket = divisao[r];
		if(l_bucket == r_bucket){
			for(int i = l;i<=r;i++){
				int j = vetor[i];
				if(versao[j] != iteracao){
					versao[j] = iteracao;
					tempfreq[j] = 0;
				}
				tempfreq[j]++;
				resp = max(resp, 1LL*tempfreq[j]*volta[j] );
			}
		}
		else{
			resp = precalc[l_bucket+1][r_bucket-1];
			for(int i = l;i < (l_bucket+1)*BUCKET;i++){
				int j = vetor[i];
				if(versao[j] != iteracao){
					versao[j] = iteracao;
					tempfreq[j] = freq[r_bucket-1][j] - freq[l_bucket][j];
				}
				tempfreq[j]++;
				resp = max(resp, 1LL*tempfreq[j]*volta[j] );
			}
			for(int i = r_bucket*BUCKET;i<=r;i++){
				int j = vetor[i];
				if(versao[j] != iteracao){
					versao[j] = iteracao;
					tempfreq[j] = freq[r_bucket-1][j] - freq[l_bucket][j];
				}
				tempfreq[j]++;
				resp = max(resp, 1LL*tempfreq[j]*volta[j] );
			}
		}
		printf("%lld\n",resp);
	}
	return 0;
}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<ida.size();i++) volta.push_back(ida[i]);
                 ^
historic.cpp:24:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&Q);
                      ^
historic.cpp:26:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&vetor[i]);
                        ^
historic.cpp:42:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&l,&r);
                       ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60