답안 #13744 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13744	2015-03-30T14:52:20 Z	gs13068	역사적 조사 (JOI14_historical)	C++	100 / 100	1085 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]);
				p[a[i]]--;
			}
			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]);
				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]];
				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	0 ms	245676 KB	Output is correct
3	Correct	0 ms	245676 KB	Output is correct
4	Correct	3 ms	245676 KB	Output is correct
5	Correct	7 ms	245676 KB	Output is correct
6	Correct	8 ms	245676 KB	Output is correct
7	Correct	6 ms	245676 KB	Output is correct
8	Correct	9 ms	245676 KB	Output is correct
9	Correct	10 ms	245676 KB	Output is correct
10	Correct	12 ms	245676 KB	Output is correct
11	Correct	8 ms	245676 KB	Output is correct
12	Correct	11 ms	245676 KB	Output is correct
13	Correct	10 ms	245676 KB	Output is correct
14	Correct	10 ms	245676 KB	Output is correct
15	Correct	13 ms	245676 KB	Output is correct
16	Correct	11 ms	245676 KB	Output is correct
17	Correct	8 ms	245676 KB	Output is correct
18	Correct	11 ms	245676 KB	Output is correct
19	Correct	8 ms	245676 KB	Output is correct
20	Correct	15 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	1 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	3 ms	245676 KB	Output is correct
8	Correct	9 ms	245676 KB	Output is correct
9	Correct	17 ms	245676 KB	Output is correct
10	Correct	22 ms	245676 KB	Output is correct
11	Correct	140 ms	245676 KB	Output is correct
12	Correct	92 ms	245676 KB	Output is correct
13	Correct	188 ms	245676 KB	Output is correct
14	Correct	372 ms	245676 KB	Output is correct
15	Correct	425 ms	245676 KB	Output is correct
16	Correct	753 ms	245676 KB	Output is correct
17	Correct	127 ms	245676 KB	Output is correct
18	Correct	203 ms	245676 KB	Output is correct
19	Correct	606 ms	245676 KB	Output is correct
20	Correct	479 ms	245676 KB	Output is correct

Subtask #4
60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	245676 KB	Output is correct
2	Correct	54 ms	245676 KB	Output is correct
3	Correct	100 ms	245676 KB	Output is correct
4	Correct	176 ms	245676 KB	Output is correct
5	Correct	277 ms	245676 KB	Output is correct
6	Correct	222 ms	245676 KB	Output is correct
7	Correct	213 ms	245676 KB	Output is correct
8	Correct	211 ms	245676 KB	Output is correct
9	Correct	226 ms	245676 KB	Output is correct
10	Correct	275 ms	245676 KB	Output is correct
11	Correct	265 ms	245676 KB	Output is correct
12	Correct	308 ms	245676 KB	Output is correct
13	Correct	484 ms	245676 KB	Output is correct
14	Correct	862 ms	245676 KB	Output is correct
15	Correct	1085 ms	245676 KB	Output is correct
16	Correct	982 ms	245676 KB	Output is correct
17	Correct	952 ms	245676 KB	Output is correct
18	Correct	896 ms	245676 KB	Output is correct
19	Correct	887 ms	245676 KB	Output is correct
20	Correct	834 ms	245676 KB	Output is correct
21	Correct	831 ms	245676 KB	Output is correct
22	Correct	831 ms	245676 KB	Output is correct
23	Correct	824 ms	245676 KB	Output is correct
24	Correct	777 ms	245676 KB	Output is correct
25	Correct	308 ms	245676 KB	Output is correct

답안 #13744

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