Submission #6792

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

historic

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

#define MAXN 101101
#define ROOT 400

int N, Q;
int X[MAXN];
int Sort[MAXN], Sortp;
int Number[MAXN][ROOT+2];

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;
	}
}
int Interval(int i) {
	return (i-1)/ROOT+1;
}
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)]++;
	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);
				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 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[Find(X[j])]!=i) {
				Stack[++Stackp]=X[j];
				Check[Find(X[j])]=i;
				Now_Number[Find(X[j])]=1;
			}else Now_Number[Find(X[j])]++;
		}
		for(int j=What(finish, ROOT+1); j<=y; j++) {
			if(Check[Find(X[j])]!=i) {
				Stack[++Stackp]=X[j];
				Check[Find(X[j])]=i;
				Now_Number[Find(X[j])]=1;
			}else Now_Number[Find(X[j])]++;
		}
		for(int j=1; j<=Stackp; j++) {
			int number=Stack[j];
			int renumber=Find(number);
			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() {
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);


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

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