답안 #13742 :: oj.uz

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

historic

#include<cstdio>
#include<algorithm>

int a[111111];
int t[111111],tn;
int c[111111][333];
long long d[333][333];
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&511))for(j=0;j<tn;j++)c[j][(i>>9)+1]=c[j][i>>9];
		c[a[i]][(i>>9)+1]++;
	}
	for(i=0;i<(n>>9);i++)
	{
		for(j=i+1;j<=(n>>9);j++)
		{
			d[i][j]=d[i][j-1];
			for(k=(j-1)<<9;k<(j<<9);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+511)>>9;
        r=e>>9;
        if(l<r)
		{
			res=d[l][r];
			for(i=s;i<(l<<9);i++)p[a[i]]++;
			for(i=r<<9;i<e;i++)p[a[i]]++;
			for(i=s;i<(l<<9);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<<9;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<<9);i++)p[a[i]]--;
			for(i=r<<9;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	147784 KB	Output is correct
2	Correct	147784 KB	Output is correct
3	Correct	147784 KB	Output is correct
4	Correct	147784 KB	Output is correct
5	Correct	147784 KB	Output is correct
6	Correct	147784 KB	Output is correct
7	Correct	147784 KB	Output is correct
8	Correct	147784 KB	Output is correct
9	Correct	147784 KB	Output is correct
10	Correct	147784 KB	Output is correct
11	Correct	147784 KB	Output is correct
12	Correct	147784 KB	Output is correct
13	Correct	147784 KB	Output is correct
14	Correct	147784 KB	Output is correct
15	Correct	147784 KB	Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	147784 KB	Output is correct
2	Correct	0 ms	147784 KB	Output is correct
3	Correct	0 ms	147784 KB	Output is correct
4	Correct	0 ms	147784 KB	Output is correct
5	Correct	0 ms	147784 KB	Output is correct
6	Correct	2 ms	147784 KB	Output is correct
7	Correct	3 ms	147784 KB	Output is correct
8	Correct	7 ms	147784 KB	Output is correct
9	Correct	18 ms	147784 KB	Output is correct
10	Correct	19 ms	147784 KB	Output is correct
11	Correct	115 ms	147784 KB	Output is correct
12	Correct	55 ms	147784 KB	Output is correct
13	Correct	151 ms	147784 KB	Output is correct
14	Correct	252 ms	147784 KB	Output is correct
15	Correct	287 ms	147784 KB	Output is correct
16	Correct	689 ms	147784 KB	Output is correct
17	Correct	162 ms	147784 KB	Output is correct
18	Correct	326 ms	147784 KB	Output is correct
19	Correct	539 ms	147784 KB	Output is correct
20	Correct	302 ms	147784 KB	Output is correct

Subtask #4
60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	147784 KB	Output is correct
2	Correct	81 ms	147784 KB	Output is correct
3	Correct	177 ms	147784 KB	Output is correct
4	Correct	284 ms	147784 KB	Output is correct
5	Correct	379 ms	147784 KB	Output is correct
6	Correct	374 ms	147784 KB	Output is correct
7	Correct	353 ms	147784 KB	Output is correct
8	Correct	359 ms	147784 KB	Output is correct
9	Correct	406 ms	147784 KB	Output is correct
10	Correct	545 ms	147784 KB	Output is correct
11	Correct	439 ms	147784 KB	Output is correct
12	Correct	506 ms	147784 KB	Output is correct
13	Correct	676 ms	147784 KB	Output is correct
14	Correct	1271 ms	147784 KB	Output is correct
15	Correct	1438 ms	147784 KB	Output is correct
16	Correct	1371 ms	147784 KB	Output is correct
17	Correct	1316 ms	147784 KB	Output is correct
18	Correct	1296 ms	147784 KB	Output is correct
19	Correct	1275 ms	147784 KB	Output is correct
20	Correct	1248 ms	147784 KB	Output is correct
21	Correct	1236 ms	147784 KB	Output is correct
22	Correct	1183 ms	147784 KB	Output is correct
23	Correct	1157 ms	147784 KB	Output is correct
24	Correct	1135 ms	147784 KB	Output is correct
25	Correct	579 ms	147784 KB	Output is correct

답안 #13742

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