답안 #6717 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6717	2014-07-05T02:43:46 Z	gs13068	역사적 조사 (JOI14_historical)	C++	100 / 100	1016 ms	201576 KB

historic

#include<cstdio>
#include<memory.h>
#include<algorithm>

#define BUCKET 200

int a[100000];
int b[100000];
int c[100000];
int d[500][100000];
long long x[500][500];

char ss[2097152];

inline int getnum()
{
    int t,r=0;
    do{t=getchar();}while(t<40);
    do{r=r*10+t-48;t=getchar();}while(t>40);
    return r;
}

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++;
        }
        b[i]=a[i];
    }
    std::sort(b,b+n);
    for(i=0;i<n;i++)a[i]=std::lower_bound(b,b+n,a[i])-b;
    for(i=0;i<n;i++)
    {
        if(i>0&&i%BUCKET==0)memcpy(d[i/BUCKET],d[i/BUCKET-1],n<<2);
        d[i/BUCKET][a[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];
            for(k=0;k<BUCKET;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]];
            }
        }
    }
    memset(c,0,n<<2);
    for(i=0;i<m;i++)
    {
        s=getnum()-1;e=getnum();
        if((s+BUCKET-1)/BUCKET<e/BUCKET)
        {
            r=x[(s+BUCKET-1)/BUCKET][e/BUCKET-1];
            for(j=s;j<(s+BUCKET-1)/BUCKET*BUCKET;j++)
			{
				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));
			}
            for(j=e/BUCKET*BUCKET;j<e;j++)
			{
				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));
			}
            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;
            for(j=s;j<e;j++)
			{
				c[a[j]]++;
				if(1LL*b[a[j]]*c[a[j]]>r)r=1LL*b[a[j]]*c[a[j]];
			}
            for(j=s;j<e;j++)c[a[j]]=0;
        }
        printf("%lld\n",r);
    }
}

Subtask #1
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	201576 KB	Output is correct
2	Correct	201576 KB	Output is correct
3	Correct	201576 KB	Output is correct
4	Correct	201576 KB	Output is correct
5	Correct	201576 KB	Output is correct
6	Correct	201576 KB	Output is correct
7	Correct	201576 KB	Output is correct
8	Correct	201576 KB	Output is correct
9	Correct	201576 KB	Output is correct
10	Correct	201576 KB	Output is correct
11	Correct	201576 KB	Output is correct
12	Correct	201576 KB	Output is correct
13	Correct	201576 KB	Output is correct
14	Correct	201576 KB	Output is correct
15	Correct	201576 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	201576 KB	Output is correct
2	Correct	0 ms	201576 KB	Output is correct
3	Correct	0 ms	201576 KB	Output is correct
4	Correct	0 ms	201576 KB	Output is correct
5	Correct	0 ms	201576 KB	Output is correct
6	Correct	4 ms	201576 KB	Output is correct
7	Correct	8 ms	201576 KB	Output is correct
8	Correct	4 ms	201576 KB	Output is correct
9	Correct	8 ms	201576 KB	Output is correct
10	Correct	4 ms	201576 KB	Output is correct
11	Correct	8 ms	201576 KB	Output is correct
12	Correct	8 ms	201576 KB	Output is correct
13	Correct	8 ms	201576 KB	Output is correct
14	Correct	8 ms	201576 KB	Output is correct
15	Correct	12 ms	201576 KB	Output is correct
16	Correct	8 ms	201576 KB	Output is correct
17	Correct	8 ms	201576 KB	Output is correct
18	Correct	12 ms	201576 KB	Output is correct
19	Correct	8 ms	201576 KB	Output is correct
20	Correct	8 ms	201576 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	201576 KB	Output is correct
2	Correct	0 ms	201576 KB	Output is correct
3	Correct	0 ms	201576 KB	Output is correct
4	Correct	0 ms	201576 KB	Output is correct
5	Correct	0 ms	201576 KB	Output is correct
6	Correct	0 ms	201576 KB	Output is correct
7	Correct	0 ms	201576 KB	Output is correct
8	Correct	0 ms	201576 KB	Output is correct
9	Correct	20 ms	201576 KB	Output is correct
10	Correct	84 ms	201576 KB	Output is correct
11	Correct	244 ms	201576 KB	Output is correct
12	Correct	164 ms	201576 KB	Output is correct
13	Correct	296 ms	201576 KB	Output is correct
14	Correct	312 ms	201576 KB	Output is correct
15	Correct	248 ms	201576 KB	Output is correct
16	Correct	324 ms	201576 KB	Output is correct
17	Correct	168 ms	201576 KB	Output is correct
18	Correct	268 ms	201576 KB	Output is correct
19	Correct	224 ms	201576 KB	Output is correct
20	Correct	152 ms	201576 KB	Output is correct

Subtask #4
60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	201576 KB	Output is correct
2	Correct	64 ms	201576 KB	Output is correct
3	Correct	168 ms	201576 KB	Output is correct
4	Correct	256 ms	201576 KB	Output is correct
5	Correct	348 ms	201576 KB	Output is correct
6	Correct	424 ms	201576 KB	Output is correct
7	Correct	412 ms	201576 KB	Output is correct
8	Correct	364 ms	201576 KB	Output is correct
9	Correct	440 ms	201576 KB	Output is correct
10	Correct	368 ms	201576 KB	Output is correct
11	Correct	476 ms	201576 KB	Output is correct
12	Correct	696 ms	201576 KB	Output is correct
13	Correct	988 ms	201576 KB	Output is correct
14	Correct	956 ms	201576 KB	Output is correct
15	Correct	964 ms	201576 KB	Output is correct
16	Correct	996 ms	201576 KB	Output is correct
17	Correct	1016 ms	201576 KB	Output is correct
18	Correct	976 ms	201576 KB	Output is correct
19	Correct	1000 ms	201576 KB	Output is correct
20	Correct	956 ms	201576 KB	Output is correct
21	Correct	984 ms	201576 KB	Output is correct
22	Correct	968 ms	201576 KB	Output is correct
23	Correct	980 ms	201576 KB	Output is correct
24	Correct	988 ms	201576 KB	Output is correct
25	Correct	328 ms	201576 KB	Output is correct

답안 #6717

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 25.0 / 25.0

Subtask #4 60.0 / 60.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
25.0 / 25.0

Subtask #4
60.0 / 60.0