#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[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);
return 0;
INPUT();
PROCESS();
OUTPUT();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
162736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
162736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
162736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
162736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
