Submission #6799

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
6799	2014-07-07T12:25:56 Z	qja0950	역사적 조사 (JOI14_historical)	C++	100 / 100	2416 ms	128768 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[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 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	128768 KB	Output is correct
2	Correct	128768 KB	Output is correct
3	Correct	128768 KB	Output is correct
4	Correct	128768 KB	Output is correct
5	Correct	128768 KB	Output is correct
6	Correct	128768 KB	Output is correct
7	Correct	128768 KB	Output is correct
8	Correct	128768 KB	Output is correct
9	Correct	128768 KB	Output is correct
10	Correct	128768 KB	Output is correct
11	Correct	128768 KB	Output is correct
12	Correct	128768 KB	Output is correct
13	Correct	128768 KB	Output is correct
14	Correct	128768 KB	Output is correct
15	Correct	128768 KB	Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	128768 KB	Output is correct
2	Correct	0 ms	128768 KB	Output is correct
3	Correct	0 ms	128768 KB	Output is correct
4	Correct	0 ms	128768 KB	Output is correct
5	Correct	0 ms	128768 KB	Output is correct
6	Correct	0 ms	128768 KB	Output is correct
7	Correct	4 ms	128768 KB	Output is correct
8	Correct	12 ms	128768 KB	Output is correct
9	Correct	32 ms	128768 KB	Output is correct
10	Correct	20 ms	128768 KB	Output is correct
11	Correct	168 ms	128768 KB	Output is correct
12	Correct	92 ms	128768 KB	Output is correct
13	Correct	476 ms	128768 KB	Output is correct
14	Correct	1232 ms	128768 KB	Output is correct
15	Correct	2260 ms	128768 KB	Output is correct
16	Correct	1260 ms	128768 KB	Output is correct
17	Correct	120 ms	128768 KB	Output is correct
18	Correct	200 ms	128768 KB	Output is correct
19	Correct	600 ms	128768 KB	Output is correct
20	Correct	420 ms	128768 KB	Output is correct

Subtask #4
60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	128768 KB	Output is correct
2	Correct	92 ms	128768 KB	Output is correct
3	Correct	260 ms	128768 KB	Output is correct
4	Correct	508 ms	128768 KB	Output is correct
5	Correct	724 ms	128768 KB	Output is correct
6	Correct	560 ms	128768 KB	Output is correct
7	Correct	332 ms	128768 KB	Output is correct
8	Correct	196 ms	128768 KB	Output is correct
9	Correct	164 ms	128768 KB	Output is correct
10	Correct	208 ms	128768 KB	Output is correct
11	Correct	200 ms	128768 KB	Output is correct
12	Correct	448 ms	128768 KB	Output is correct
13	Correct	1152 ms	128768 KB	Output is correct
14	Correct	2056 ms	128768 KB	Output is correct
15	Correct	2416 ms	128768 KB	Output is correct
16	Correct	2268 ms	128768 KB	Output is correct
17	Correct	2192 ms	128768 KB	Output is correct
18	Correct	2124 ms	128768 KB	Output is correct
19	Correct	2036 ms	128768 KB	Output is correct
20	Correct	2072 ms	128768 KB	Output is correct
21	Correct	2032 ms	128768 KB	Output is correct
22	Correct	2048 ms	128768 KB	Output is correct
23	Correct	2040 ms	128768 KB	Output is correct
24	Correct	2000 ms	128768 KB	Output is correct
25	Correct	224 ms	128768 KB	Output is correct

Submission #6799

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