oj.uz

Submission #6790

# Submission time Handle Problem Language Result Execution time Memory
6790 2014-07-07T11:56:37 Z qja0950 역사적 조사 (JOI14_historical) C++
5 / 100
 4000 ms 162740 KB 
#include <stdio.h>
#include <algorithm>
using namespace std;

#define MAXN 101101
#define ROOT 400

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[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);
	INPUT();
	PROCESS();
	OUTPUT();
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 162740 KB Output is correct
2 Correct 12 ms 162740 KB Output is correct
3 Correct 28 ms 162740 KB Output is correct
4 Correct 68 ms 162740 KB Output is correct
5 Correct 156 ms 162740 KB Output is correct
6 Correct 188 ms 162740 KB Output is correct
7 Correct 264 ms 162740 KB Output is correct
8 Correct 96 ms 162740 KB Output is correct
9 Correct 108 ms 162740 KB Output is correct
10 Incorrect 640 ms 162740 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 162740 KB Output is correct
2 Correct 0 ms 162740 KB Output is correct
3 Correct 0 ms 162740 KB Output is correct
4 Correct 0 ms 162740 KB Output is correct
5 Correct 92 ms 162740 KB Output is correct
6 Correct 4 ms 162740 KB Output is correct
7 Correct 20 ms 162740 KB Output is correct
8 Correct 24 ms 162740 KB Output is correct
9 Correct 124 ms 162740 KB Output is correct
10 Correct 52 ms 162740 KB Output is correct
11 Correct 1416 ms 162740 KB Output is correct
12 Correct 820 ms 162740 KB Output is correct
13 Execution timed out 4000 ms 162740 KB Program timed out
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 162740 KB Output is correct
2 Correct 1828 ms 162740 KB Output is correct
3 Execution timed out 4000 ms 162740 KB Program timed out
4 Halted 0 ms 0 KB -