답안 #13743 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13743	2015-03-30T14:51:08 Z	gs13068	역사적 조사 (JOI14_historical)	C++	100 / 100	1066 ms	245676 KB

historic

#include<cstdio>
#include<algorithm>

int a[111111];
int t[111111],tn;
int c[111111][555];
long long d[555][555];
int p[111111];

int main()
{
	long long res;
    int i,j,k,s,e,n,m,l,r;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		t[i]=a[i];
	}
	std::sort(t,t+n);
	tn=std::unique(t,t+n)-t;
    for(i=0;i<n;i++)a[i]=std::lower_bound(t,t+tn,a[i])-t;
	for(i=0;i<n;i++)
	{
		if(!(i&255))for(j=0;j<tn;j++)c[j][(i>>8)+1]=c[j][i>>8];
		c[a[i]][(i>>8)+1]++;
	}
	for(i=0;i<(n>>8);i++)
	{
		for(j=i+1;j<=(n>>8);j++)
		{
			d[i][j]=d[i][j-1];
			for(k=(j-1)<<8;k<(j<<8);k++)if(1LL*t[a[k]]*(c[a[k]][j]-c[a[k]][i])>d[i][j])d[i][j]=1LL*t[a[k]]*(c[a[k]][j]-c[a[k]][i]);
		}
	}
	while(m--)
	{
		scanf("%d%d",&s,&e);
        s--;
        l=(s+255)>>8;
        r=e>>8;
        if(l<r)
		{
			res=d[l][r];
			for(i=s;i<(l<<8);i++)p[a[i]]++;
			for(i=r<<8;i<e;i++)p[a[i]]++;
			for(i=s;i<(l<<8);i++)if(1LL*t[a[i]]*(p[a[i]]+c[a[i]][r]-c[a[i]][l])>res)res=1LL*t[a[i]]*(p[a[i]]+c[a[i]][r]-c[a[i]][l]);
			for(i=r<<8;i<e;i++)if(1LL*t[a[i]]*(p[a[i]]+c[a[i]][r]-c[a[i]][l])>res)res=1LL*t[a[i]]*(p[a[i]]+c[a[i]][r]-c[a[i]][l]);
			for(i=s;i<(l<<8);i++)p[a[i]]--;
			for(i=r<<8;i<e;i++)p[a[i]]--;
		}
		else
		{
			res=0;
			for(i=s;i<e;i++)p[a[i]]++;
			for(i=s;i<e;i++)if(1LL*t[a[i]]*p[a[i]]>res)res=1LL*t[a[i]]*p[a[i]];
			for(i=s;i<e;i++)p[a[i]]--;
		}
		printf("%lld\n",res);
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	245676 KB	Output is correct
2	Correct	0 ms	245676 KB	Output is correct
3	Correct	0 ms	245676 KB	Output is correct
4	Correct	0 ms	245676 KB	Output is correct
5	Correct	0 ms	245676 KB	Output is correct
6	Correct	0 ms	245676 KB	Output is correct
7	Correct	0 ms	245676 KB	Output is correct
8	Correct	9 ms	245676 KB	Output is correct
9	Correct	24 ms	245676 KB	Output is correct
10	Correct	20 ms	245676 KB	Output is correct
11	Correct	137 ms	245676 KB	Output is correct
12	Correct	90 ms	245676 KB	Output is correct
13	Correct	205 ms	245676 KB	Output is correct
14	Correct	385 ms	245676 KB	Output is correct
15	Correct	414 ms	245676 KB	Output is correct
16	Correct	788 ms	245676 KB	Output is correct
17	Correct	133 ms	245676 KB	Output is correct
18	Correct	217 ms	245676 KB	Output is correct
19	Correct	614 ms	245676 KB	Output is correct
20	Correct	480 ms	245676 KB	Output is correct

Subtask #4
60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	245676 KB	Output is correct
2	Correct	52 ms	245676 KB	Output is correct
3	Correct	109 ms	245676 KB	Output is correct
4	Correct	188 ms	245676 KB	Output is correct
5	Correct	278 ms	245676 KB	Output is correct
6	Correct	250 ms	245676 KB	Output is correct
7	Correct	234 ms	245676 KB	Output is correct
8	Correct	217 ms	245676 KB	Output is correct
9	Correct	253 ms	245676 KB	Output is correct
10	Correct	336 ms	245676 KB	Output is correct
11	Correct	286 ms	245676 KB	Output is correct
12	Correct	347 ms	245676 KB	Output is correct
13	Correct	534 ms	245676 KB	Output is correct
14	Correct	868 ms	245676 KB	Output is correct
15	Correct	1066 ms	245676 KB	Output is correct
16	Correct	975 ms	245676 KB	Output is correct
17	Correct	927 ms	245676 KB	Output is correct
18	Correct	899 ms	245676 KB	Output is correct
19	Correct	890 ms	245676 KB	Output is correct
20	Correct	849 ms	245676 KB	Output is correct
21	Correct	844 ms	245676 KB	Output is correct
22	Correct	830 ms	245676 KB	Output is correct
23	Correct	812 ms	245676 KB	Output is correct
24	Correct	813 ms	245676 KB	Output is correct
25	Correct	346 ms	245676 KB	Output is correct

답안 #13743

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