oj.uz

Submission #6793

# Submission time Handle Problem Language Result Execution time Memory
6793 2014-07-07T12:07:12 Z qja0950 역사적 조사 (JOI14_historical) C++
15 / 100
 4000 ms 162744 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[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);

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 162744 KB Output is correct
2 Correct 0 ms 162744 KB Output is correct
3 Correct 0 ms 162744 KB Output is correct
4 Correct 0 ms 162744 KB Output is correct
5 Correct 0 ms 162744 KB Output is correct
6 Correct 0 ms 162744 KB Output is correct
7 Correct 0 ms 162744 KB Output is correct
8 Correct 0 ms 162744 KB Output is correct
9 Correct 0 ms 162744 KB Output is correct
10 Correct 0 ms 162744 KB Output is correct
11 Correct 0 ms 162744 KB Output is correct
12 Correct 0 ms 162744 KB Output is correct
13 Correct 0 ms 162744 KB Output is correct
14 Correct 0 ms 162744 KB Output is correct
15 Correct 0 ms 162744 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 162744 KB Output is correct
2 Correct 12 ms 162744 KB Output is correct
3 Correct 32 ms 162744 KB Output is correct
4 Correct 64 ms 162744 KB Output is correct
5 Correct 156 ms 162744 KB Output is correct
6 Correct 188 ms 162744 KB Output is correct
7 Correct 264 ms 162744 KB Output is correct
8 Correct 96 ms 162744 KB Output is correct
9 Correct 112 ms 162744 KB Output is correct
10 Correct 632 ms 162744 KB Output is correct
11 Correct 604 ms 162744 KB Output is correct
12 Correct 592 ms 162744 KB Output is correct
13 Correct 568 ms 162744 KB Output is correct
14 Correct 500 ms 162744 KB Output is correct
15 Correct 544 ms 162744 KB Output is correct
16 Correct 112 ms 162744 KB Output is correct
17 Correct 40 ms 162744 KB Output is correct
18 Correct 536 ms 162744 KB Output is correct
19 Correct 656 ms 162744 KB Output is correct
20 Correct 676 ms 162744 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 162744 KB Output is correct
2 Correct 0 ms 162744 KB Output is correct
3 Correct 0 ms 162744 KB Output is correct
4 Correct 0 ms 162744 KB Output is correct
5 Correct 92 ms 162744 KB Output is correct
6 Correct 4 ms 162744 KB Output is correct
7 Correct 16 ms 162744 KB Output is correct
8 Correct 24 ms 162744 KB Output is correct
9 Correct 120 ms 162744 KB Output is correct
10 Correct 52 ms 162744 KB Output is correct
11 Correct 1472 ms 162744 KB Output is correct
12 Correct 820 ms 162744 KB Output is correct
13 Execution timed out 4000 ms 162744 KB Program timed out
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 162744 KB Output is correct
2 Correct 1828 ms 162744 KB Output is correct
3 Execution timed out 4000 ms 162744 KB Program timed out
4 Halted 0 ms 0 KB -