oj.uz

Submission #6796

# Submission time Handle Problem Language Result Execution time Memory
6796 2014-07-07T12:14:40 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];

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 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 32 ms 135084 KB Output is correct
6 Correct 28 ms 135084 KB Output is correct
7 Correct 52 ms 135084 KB Output is correct
8 Correct 16 ms 135084 KB Output is correct
9 Correct 16 ms 135084 KB Output is correct
10 Correct 140 ms 135084 KB Output is correct
11 Correct 136 ms 135084 KB Output is correct
12 Correct 124 ms 135084 KB Output is correct
13 Correct 116 ms 135084 KB Output is correct
14 Correct 108 ms 135084 KB Output is correct
15 Correct 116 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 116 ms 135084 KB Output is correct
19 Correct 144 ms 135084 KB Output is correct
20 Correct 144 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 12 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 8 ms 135084 KB Output is correct
9 Correct 28 ms 135084 KB Output is correct
10 Correct 20 ms 135084 KB Output is correct
11 Correct 200 ms 135084 KB Output is correct
12 Correct 88 ms 135084 KB Output is correct
13 Correct 1080 ms 135084 KB Output is correct
14 Correct 3272 ms 135084 KB Output is correct
15 Halted 0 ms 0 KB -1: Interrupted system call
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 388 ms 135084 KB Output is correct
3 Correct 1132 ms 135084 KB Output is correct
4 Correct 1956 ms 135084 KB Output is correct
5 Correct 2708 ms 135084 KB Output is correct
6 Correct 2260 ms 135084 KB Output is correct
7 Correct 1148 ms 135084 KB Output is correct
8 Correct 308 ms 135084 KB Output is correct
9 Correct 188 ms 135084 KB Output is correct
10 Correct 212 ms 135084 KB Output is correct
11 Correct 232 ms 135084 KB Output is correct
12 Correct 1336 ms 135084 KB Output is correct
13 Execution timed out 4000 ms 135084 KB Program timed out
14 Halted 0 ms 0 KB -