#include<cstdio>
#include<ctime>
#include<memory.h>
#include<algorithm>
#define BUCKET 200
int a[131072];
int b[131072];
int c[131072];
int d[512][131072];
long long x[512][512];
char ss[2097152];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
char *p;
long long r;
int s,e,t;
int i,j,k,n,m;
scanf("%d %d\n",&n,&m);
fgets(ss,2097151,stdin);
p=ss;
for(i=0;i<n;i++)
{
while(*p<40)p++;
while(*p>40)
{
a[i]=a[i]*10+*p-48;
p++;
}
}
memcpy(b,a,n<<2);
std::sort(b,b+n);
for(i=0;i<n;i++)a[i]=std::lower_bound(b,b+n,a[i])-b;
i=0;
while(i<n)
{
if(i>0&&i%BUCKET==0)memcpy(d[i/BUCKET],d[i/BUCKET-1],n<<2);
d[i/BUCKET][a[i]]++;
i++;
if(i>0&&i%BUCKET==0)memcpy(d[i/BUCKET],d[i/BUCKET-1],n<<2);
d[i/BUCKET][a[i]]++;
i++;
if(i>0&&i%BUCKET==0)memcpy(d[i/BUCKET],d[i/BUCKET-1],n<<2);
d[i/BUCKET][a[i]]++;
i++;
if(i>0&&i%BUCKET==0)memcpy(d[i/BUCKET],d[i/BUCKET-1],n<<2);
d[i/BUCKET][a[i]]++;
i++;
if(i>0&&i%BUCKET==0)memcpy(d[i/BUCKET],d[i/BUCKET-1],n<<2);
d[i/BUCKET][a[i]]++;
i++;
if(i>0&&i%BUCKET==0)memcpy(d[i/BUCKET],d[i/BUCKET-1],n<<2);
d[i/BUCKET][a[i]]++;
i++;
if(i>0&&i%BUCKET==0)memcpy(d[i/BUCKET],d[i/BUCKET-1],n<<2);
d[i/BUCKET][a[i]]++;
i++;
if(i>0&&i%BUCKET==0)memcpy(d[i/BUCKET],d[i/BUCKET-1],n<<2);
d[i/BUCKET][a[i]]++;
i++;
}
for(i=0;i<n/BUCKET;i++)
{
memset(c,0,n<<2);
for(j=i;j<n/BUCKET;j++)
{
if(j>i)x[i][j]=x[i][j-1];
k=0;
while(k<BUCKET)
{
t=j*BUCKET+k;
c[a[t]]++;
if(1LL*b[a[t]]*c[a[t]]>x[i][j])x[i][j]=1LL*b[a[t]]*c[a[t]];
k++;
t=j*BUCKET+k;
c[a[t]]++;
if(1LL*b[a[t]]*c[a[t]]>x[i][j])x[i][j]=1LL*b[a[t]]*c[a[t]];
k++;
t=j*BUCKET+k;
c[a[t]]++;
if(1LL*b[a[t]]*c[a[t]]>x[i][j])x[i][j]=1LL*b[a[t]]*c[a[t]];
k++;
t=j*BUCKET+k;
c[a[t]]++;
if(1LL*b[a[t]]*c[a[t]]>x[i][j])x[i][j]=1LL*b[a[t]]*c[a[t]];
k++;
t=j*BUCKET+k;
c[a[t]]++;
if(1LL*b[a[t]]*c[a[t]]>x[i][j])x[i][j]=1LL*b[a[t]]*c[a[t]];
k++;
t=j*BUCKET+k;
c[a[t]]++;
if(1LL*b[a[t]]*c[a[t]]>x[i][j])x[i][j]=1LL*b[a[t]]*c[a[t]];
k++;
t=j*BUCKET+k;
c[a[t]]++;
if(1LL*b[a[t]]*c[a[t]]>x[i][j])x[i][j]=1LL*b[a[t]]*c[a[t]];
k++;
t=j*BUCKET+k;
c[a[t]]++;
if(1LL*b[a[t]]*c[a[t]]>x[i][j])x[i][j]=1LL*b[a[t]]*c[a[t]];
k++;
}
}
}
memset(c,0,n<<2);
for(i=0;i<m;i++)
{
s=0;
do{t=getchar();}while(t<40);
do{s=s*10+t-48;t=getchar();}while(t>40);
s--;
e=0;
do{t=getchar();}while(t<40);
do{e=e*10+t-48;t=getchar();}while(t>40);
if((s+BUCKET-1)/BUCKET<e/BUCKET)
{
r=x[(s+BUCKET-1)/BUCKET][e/BUCKET-1];
j=s;
while(1)
{
if(j>=(s+BUCKET-1)/BUCKET*BUCKET)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=(s+BUCKET-1)/BUCKET*BUCKET)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=(s+BUCKET-1)/BUCKET*BUCKET)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=(s+BUCKET-1)/BUCKET*BUCKET)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=(s+BUCKET-1)/BUCKET*BUCKET)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=(s+BUCKET-1)/BUCKET*BUCKET)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=(s+BUCKET-1)/BUCKET*BUCKET)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=(s+BUCKET-1)/BUCKET*BUCKET)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
}
j=e/BUCKET*BUCKET;
while(1)
{
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0))>r)r=1LL*b[a[j]]*(c[a[j]]+d[e/BUCKET-1][a[j]]-((s+BUCKET-1)/BUCKET>0?d[(s+BUCKET-1)/BUCKET-1][a[j]]:0));
j++;
}
for(j=s;j<(s+BUCKET-1)/BUCKET*BUCKET;j++)c[a[j]]=0;
for(j=e/BUCKET*BUCKET;j<e;j++)c[a[j]]=0;
}
else
{
r=0;
j=s;
while(1)
{
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*c[a[j]]>r)r=1LL*b[a[j]]*c[a[j]];
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*c[a[j]]>r)r=1LL*b[a[j]]*c[a[j]];
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*c[a[j]]>r)r=1LL*b[a[j]]*c[a[j]];
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*c[a[j]]>r)r=1LL*b[a[j]]*c[a[j]];
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*c[a[j]]>r)r=1LL*b[a[j]]*c[a[j]];
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*c[a[j]]>r)r=1LL*b[a[j]]*c[a[j]];
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*c[a[j]]>r)r=1LL*b[a[j]]*c[a[j]];
j++;
if(j>=e)break;
c[a[j]]++;
if(1LL*b[a[j]]*c[a[j]]>r)r=1LL*b[a[j]]*c[a[j]];
j++;
}
for(j=s;j<e;j++)c[a[j]]=0;
}
printf("%lld\n",r);
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
0 ms |
268864 KB |
open (syscall #2) was called by the program (disallowed syscall) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
0 ms |
268864 KB |
open (syscall #2) was called by the program (disallowed syscall) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
0 ms |
268864 KB |
open (syscall #2) was called by the program (disallowed syscall) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
0 ms |
268864 KB |
open (syscall #2) was called by the program (disallowed syscall) |
2 |
Halted |
0 ms |
0 KB |
- |