oj.uz

Submission #6794

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 134688 KB Output is correct
2 Correct 8 ms 134688 KB Output is correct
3 Correct 20 ms 134688 KB Output is correct
4 Correct 56 ms 134688 KB Output is correct
5 Correct 128 ms 134688 KB Output is correct
6 Correct 160 ms 134688 KB Output is correct
7 Correct 232 ms 134688 KB Output is correct
8 Correct 88 ms 134688 KB Output is correct
9 Correct 96 ms 134688 KB Output is correct
10 Correct 532 ms 134688 KB Output is correct
11 Correct 528 ms 134688 KB Output is correct
12 Correct 500 ms 134688 KB Output is correct
13 Correct 484 ms 134688 KB Output is correct
14 Correct 436 ms 134688 KB Output is correct
15 Correct 464 ms 134688 KB Output is correct
16 Correct 104 ms 134688 KB Output is correct
17 Correct 28 ms 134688 KB Output is correct
18 Correct 460 ms 134688 KB Output is correct
19 Correct 556 ms 134688 KB Output is correct
20 Correct 572 ms 134688 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 134688 KB Output is correct
2 Correct 0 ms 134688 KB Output is correct
3 Correct 0 ms 134688 KB Output is correct
4 Correct 0 ms 134688 KB Output is correct
5 Correct 76 ms 134688 KB Output is correct
6 Correct 4 ms 134688 KB Output is correct
7 Correct 20 ms 134688 KB Output is correct
8 Correct 32 ms 134688 KB Output is correct
9 Correct 152 ms 134688 KB Output is correct
10 Correct 64 ms 134688 KB Output is correct
11 Correct 1336 ms 134688 KB Output is correct
12 Correct 1036 ms 134688 KB Output is correct
13 Halted 0 ms 0 KB -1: Interrupted system call
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 134688 KB Output is correct
2 Correct 1596 ms 134688 KB Output is correct
3 Halted 0 ms 0 KB -1: Interrupted system call
4 Halted 0 ms 0 KB -