Submission #6798

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
6798	2014-07-07T12:23:12 Z	qja0950	역사적 조사 (JOI14_historical)	C++	100 / 100	2392 ms	128644 KB

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[MAXN/ROOT+10][MAXN/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.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	128644 KB	Output is correct
2	Correct	0 ms	128644 KB	Output is correct
3	Correct	0 ms	128644 KB	Output is correct
4	Correct	0 ms	128644 KB	Output is correct
5	Correct	4 ms	128644 KB	Output is correct
6	Correct	0 ms	128644 KB	Output is correct
7	Correct	4 ms	128644 KB	Output is correct
8	Correct	8 ms	128644 KB	Output is correct
9	Correct	28 ms	128644 KB	Output is correct
10	Correct	20 ms	128644 KB	Output is correct
11	Correct	176 ms	128644 KB	Output is correct
12	Correct	92 ms	128644 KB	Output is correct
13	Correct	444 ms	128644 KB	Output is correct
14	Correct	1228 ms	128644 KB	Output is correct
15	Correct	2248 ms	128644 KB	Output is correct
16	Correct	1276 ms	128644 KB	Output is correct
17	Correct	124 ms	128644 KB	Output is correct
18	Correct	196 ms	128644 KB	Output is correct
19	Correct	584 ms	128644 KB	Output is correct
20	Correct	388 ms	128644 KB	Output is correct

Subtask #4
60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	128644 KB	Output is correct
2	Correct	80 ms	128644 KB	Output is correct
3	Correct	244 ms	128644 KB	Output is correct
4	Correct	504 ms	128644 KB	Output is correct
5	Correct	736 ms	128644 KB	Output is correct
6	Correct	548 ms	128644 KB	Output is correct
7	Correct	324 ms	128644 KB	Output is correct
8	Correct	184 ms	128644 KB	Output is correct
9	Correct	172 ms	128644 KB	Output is correct
10	Correct	204 ms	128644 KB	Output is correct
11	Correct	192 ms	128644 KB	Output is correct
12	Correct	444 ms	128644 KB	Output is correct
13	Correct	1144 ms	128644 KB	Output is correct
14	Correct	2060 ms	128644 KB	Output is correct
15	Correct	2392 ms	128644 KB	Output is correct
16	Correct	2256 ms	128644 KB	Output is correct
17	Correct	2192 ms	128644 KB	Output is correct
18	Correct	2160 ms	128644 KB	Output is correct
19	Correct	2096 ms	128644 KB	Output is correct
20	Correct	2000 ms	128644 KB	Output is correct
21	Correct	1984 ms	128644 KB	Output is correct
22	Correct	1996 ms	128644 KB	Output is correct
23	Correct	1912 ms	128644 KB	Output is correct
24	Correct	1864 ms	128644 KB	Output is correct
25	Correct	224 ms	128644 KB	Output is correct

Submission #6798

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 25.0 / 25.0

Subtask #4 60.0 / 60.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
25.0 / 25.0

Subtask #4
60.0 / 60.0