Submission #6799

#	Time	Username	Problem	Language	Result	Execution time	Memory
6799		qja0950	역사적 조사 (JOI14_historical)	C++98	100 / 100	2416 ms	128768 KiB

historic

#include <stdio.h>
#include <algorithm>
using namespace std;

#define MAXN 101101
#define ROOT 330

int N, Q;
int X[MAXN];
int Sort[MAXN], Sortp;
int Number[MAXN][MAXN/ROOT+10];
int Change[MAXN];

inline int Find(int k) {
	int a=1, b=Sortp, m;
	while(a<=b) {
		m=(a+b)/2;
		if(Sort[m]<k) a=m+1;
		if(Sort[m]>k) b=m-1;
		if(Sort[m]==k) return m;
	}
}
inline int Interval(int i) {
	return (i-1)/ROOT+1;
}
inline int What(int interval, int kth) {
	return (interval-1)*ROOT+kth;
}
void INPUT() {
	scanf("%d %d", &N, &Q);
	for(int i=1; i<=N; i++) {
		scanf("%d", &X[i]);
		Sort[i]=X[i];
	}
	sort(Sort+1, Sort+1+N);
	for(int i=1; i<=N; i++) {
		if(Sort[i]==Sort[i-1]) continue;
		else Sort[++Sortp]=Sort[i];
	}
	for(int i=1; i<=N; i++) {
		Number[Find(X[i])][Interval(i)]++;
		Change[i]=Find(X[i]);
	}
	for(int i=1; i<=Sortp; i++)
		for(int j=1; j<=Interval(N); j++)
			Number[i][j]+=Number[i][j-1];
}
long long Dy[ROOT+10][ROOT+10];
void PROCESS() {
	for(int i=1; i<=Interval(N); i++) {
		for(int j=i; j<=Interval(N); j++) {
			Dy[i][j]=Dy[i][j-1];
			for(int k=1; k<=ROOT; k++) {
				if(What(j, k)>N) continue;
				int number=X[What(j, k)];
//				int renumber=Find(number);
				int renumber=Change[What(j,k)];
				long long How=Number[renumber][j]-Number[renumber][i-1];
				if(Dy[i][j]<How*(long long)number)
					Dy[i][j]=How*(long long)number;
			}
		}
	}
}
int Check[MAXN];
int Stackz[3*ROOT];
int Stack[3*ROOT], Stackp;
int Now_Number[MAXN];
void OUTPUT() {
	for(int i=1; i<=Q; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		int started=Interval(x-1)+1, finish=Interval(y+1)-1;
		long long ans=Dy[started][finish];
		Stackp=0;
		for(int j=x; j<=What(started,0); j++) {
			if(j>N) continue;
			if(Check[Change[j]]!=i) {
				Stack[++Stackp]=X[j];
				Stackz[Stackp]=j;
				Check[Change[j]]=i;
				Now_Number[Change[j]]=1;
			}else Now_Number[Change[j]]++;
		}
		for(int j=What(finish, ROOT+1); j<=y; j++) {
			if(Check[Change[j]]!=i) {
				Stack[++Stackp]=X[j];
				Stackz[Stackp]=j;
				Check[Change[j]]=i;
				Now_Number[Change[j]]=1;
			}else Now_Number[Change[j]]++;
		}
		for(int j=1; j<=Stackp; j++) {
			int number=Stack[j];
			int renumber=Change[Stackz[j]];
			long long How=Number[renumber][finish]-Number[renumber][started-1]
							+Now_Number[renumber];
			if(ans<How*(long long)number)
				ans=How*(long long)number;
		}
		printf("%lld\n", ans);
	}
}
int main() {

	INPUT();
	PROCESS();
	OUTPUT();
	return 0;
}

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