답안 #6719 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6719	2014-07-05T03:07:04 Z	gs13068	역사적 조사 (JOI14_historical)	C++	0 / 100	0 ms	268864 KB
historic
#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;
}
Subtask #1
0.0 / 5.0

#	결과	실행 시간	메모리	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	-
Subtask #2
0.0 / 10.0

#	결과	실행 시간	메모리	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	-
Subtask #3
0.0 / 25.0

#	결과	실행 시간	메모리	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	-
Subtask #4
0.0 / 60.0

#	결과	실행 시간	메모리	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	-
답안 #6719

Compilation message

Subtask #1 0.0 / 5.0

Subtask #2 0.0 / 10.0

Subtask #3 0.0 / 25.0

Subtask #4 0.0 / 60.0

Subtask #1
0.0 / 5.0

Subtask #2
0.0 / 10.0

Subtask #3
0.0 / 25.0

Subtask #4
0.0 / 60.0
