oj.uz

Submission #6720

# Submission time Handle Problem Language Result Execution time Memory
6720 2014-07-05T03:07:25 Z gs13068 역사적 조사 (JOI14_historical) C++
100 / 100
 1088 ms 268872 KB 
#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()
{
    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
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 268872 KB Output is correct
2 Correct 0 ms 268872 KB Output is correct
3 Correct 0 ms 268872 KB Output is correct
4 Correct 0 ms 268872 KB Output is correct
5 Correct 0 ms 268872 KB Output is correct
6 Correct 0 ms 268872 KB Output is correct
7 Correct 0 ms 268872 KB Output is correct
8 Correct 4 ms 268872 KB Output is correct
9 Correct 8 ms 268872 KB Output is correct
10 Correct 80 ms 268872 KB Output is correct
11 Correct 232 ms 268872 KB Output is correct
12 Correct 184 ms 268872 KB Output is correct
13 Correct 332 ms 268872 KB Output is correct
14 Correct 360 ms 268872 KB Output is correct
15 Correct 264 ms 268872 KB Output is correct
16 Correct 404 ms 268872 KB Output is correct
17 Correct 300 ms 268872 KB Output is correct
18 Correct 400 ms 268872 KB Output is correct
19 Correct 320 ms 268872 KB Output is correct
20 Correct 180 ms 268872 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 268872 KB Output is correct
2 Correct 68 ms 268872 KB Output is correct
3 Correct 184 ms 268872 KB Output is correct
4 Correct 280 ms 268872 KB Output is correct
5 Correct 376 ms 268872 KB Output is correct
6 Correct 480 ms 268872 KB Output is correct
7 Correct 488 ms 268872 KB Output is correct
8 Correct 428 ms 268872 KB Output is correct
9 Correct 500 ms 268872 KB Output is correct
10 Correct 428 ms 268872 KB Output is correct
11 Correct 540 ms 268872 KB Output is correct
12 Correct 772 ms 268872 KB Output is correct
13 Correct 1044 ms 268872 KB Output is correct
14 Correct 1076 ms 268872 KB Output is correct
15 Correct 1060 ms 268872 KB Output is correct
16 Correct 1068 ms 268872 KB Output is correct
17 Correct 1072 ms 268872 KB Output is correct
18 Correct 1040 ms 268872 KB Output is correct
19 Correct 1068 ms 268872 KB Output is correct
20 Correct 1064 ms 268872 KB Output is correct
21 Correct 1044 ms 268872 KB Output is correct
22 Correct 1052 ms 268872 KB Output is correct
23 Correct 1060 ms 268872 KB Output is correct
24 Correct 1088 ms 268872 KB Output is correct
25 Correct 372 ms 268872 KB Output is correct