oj.uz

Submission #6795

# Submission time Handle Problem Language Result Execution time Memory
6795 2014-07-07T12:13:08 Z qja0950 역사적 조사 (JOI14_historical) C++
15 / 100
 4000 ms 135084 KB 
#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][ROOT+2];
int Change[MAXN];

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)]++;
		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 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];
				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];
				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=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 135084 KB Output is correct
2 Correct 0 ms 135084 KB Output is correct
3 Correct 0 ms 135084 KB Output is correct
4 Correct 0 ms 135084 KB Output is correct
5 Correct 0 ms 135084 KB Output is correct
6 Correct 0 ms 135084 KB Output is correct
7 Correct 0 ms 135084 KB Output is correct
8 Correct 0 ms 135084 KB Output is correct
9 Correct 0 ms 135084 KB Output is correct
10 Correct 0 ms 135084 KB Output is correct
11 Correct 0 ms 135084 KB Output is correct
12 Correct 0 ms 135084 KB Output is correct
13 Correct 0 ms 135084 KB Output is correct
14 Correct 0 ms 135084 KB Output is correct
15 Correct 0 ms 135084 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 135084 KB Output is correct
2 Correct 0 ms 135084 KB Output is correct
3 Correct 4 ms 135084 KB Output is correct
4 Correct 12 ms 135084 KB Output is correct
5 Correct 28 ms 135084 KB Output is correct
6 Correct 36 ms 135084 KB Output is correct
7 Correct 52 ms 135084 KB Output is correct
8 Correct 12 ms 135084 KB Output is correct
9 Correct 16 ms 135084 KB Output is correct
10 Correct 136 ms 135084 KB Output is correct
11 Correct 132 ms 135084 KB Output is correct
12 Correct 128 ms 135084 KB Output is correct
13 Correct 124 ms 135084 KB Output is correct
14 Correct 104 ms 135084 KB Output is correct
15 Correct 112 ms 135084 KB Output is correct
16 Correct 20 ms 135084 KB Output is correct
17 Correct 4 ms 135084 KB Output is correct
18 Correct 112 ms 135084 KB Output is correct
19 Correct 148 ms 135084 KB Output is correct
20 Correct 152 ms 135084 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 135084 KB Output is correct
2 Correct 0 ms 135084 KB Output is correct
3 Correct 0 ms 135084 KB Output is correct
4 Correct 0 ms 135084 KB Output is correct
5 Correct 16 ms 135084 KB Output is correct
6 Correct 0 ms 135084 KB Output is correct
7 Correct 4 ms 135084 KB Output is correct
8 Correct 12 ms 135084 KB Output is correct
9 Correct 32 ms 135084 KB Output is correct
10 Correct 20 ms 135084 KB Output is correct
11 Correct 196 ms 135084 KB Output is correct
12 Correct 96 ms 135084 KB Output is correct
13 Correct 1120 ms 135084 KB Output is correct
14 Correct 3360 ms 135084 KB Output is correct
15 Execution timed out 4000 ms 135084 KB Program timed out
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 135084 KB Output is correct
2 Correct 392 ms 135084 KB Output is correct
3 Correct 1120 ms 135084 KB Output is correct
4 Correct 2040 ms 135084 KB Output is correct
5 Correct 2728 ms 135084 KB Output is correct
6 Correct 2352 ms 135084 KB Output is correct
7 Correct 1184 ms 135084 KB Output is correct
8 Correct 324 ms 135084 KB Output is correct
9 Correct 192 ms 135084 KB Output is correct
10 Correct 208 ms 135084 KB Output is correct
11 Correct 240 ms 135084 KB Output is correct
12 Correct 1352 ms 135084 KB Output is correct
13 Execution timed out 4000 ms 135084 KB Program timed out
14 Halted 0 ms 0 KB -