oj.uz

Submission #6789

# Submission time Handle Problem Language Result Execution time Memory
6789 2014-07-07T11:30:30 Z qja0950 역사적 조사 (JOI14_historical) C++
0 / 100
 1116 ms 162740 KB 
#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[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];
//		printf("<%d : %d // %d : %d\n", x-1, started, y+1, finish);

		Stackp=0;
		for(int j=x; j<=What(started,0); j++) {
			if(j>N) continue;
			if(Check[X[j]]!=i) {
				Stack[++Stackp]=X[j];
				Check[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[X[j]]!=i) {
				Stack[++Stackp]=X[j];
				Check[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() {
	INPUT();
	PROCESS();
	OUTPUT();
	return 0;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 162740 KB Output is correct
2 Runtime error 0 ms 162736 KB SIGSEGV Segmentation fault
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 162740 KB Output is correct
2 Correct 8 ms 162740 KB Output is correct
3 Runtime error 0 ms 162736 KB SIGSEGV Segmentation fault
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 162740 KB Output is correct
2 Correct 0 ms 162740 KB Output is correct
3 Correct 0 ms 162740 KB Output is correct
4 Correct 0 ms 162740 KB Output is correct
5 Correct 52 ms 162740 KB Output is correct
6 Runtime error 0 ms 162736 KB SIGSEGV Segmentation fault
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 162740 KB Output is correct
2 Incorrect 1116 ms 162740 KB Output isn't correct
3 Halted 0 ms 0 KB -