답안 #13746 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13746	2015-03-30T15:00:27 Z	gs13068	역사적 조사 (JOI14_historical)	C++	100 / 100	888 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];
			for(j=0;j<(i>>8);j++)d[j][(i>>8)+1]=d[j][i>>8];
		}
		c[a[i]][(i>>8)+1]++;
		for(j=0;j<=(i>>8);j++)if(1LL*t[a[i]]*(c[a[i]][(i>>8)+1]-c[a[i]][j])>d[j][(i>>8)+1])d[j][(i>>8)+1]=1LL*t[a[i]]*(c[a[i]][(i>>8)+1]-c[a[i]][j]);
	}
	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	0 ms	245676 KB	Output is correct
5	Correct	6 ms	245676 KB	Output is correct
6	Correct	11 ms	245676 KB	Output is correct
7	Correct	6 ms	245676 KB	Output is correct
8	Correct	8 ms	245676 KB	Output is correct
9	Correct	7 ms	245676 KB	Output is correct
10	Correct	11 ms	245676 KB	Output is correct
11	Correct	9 ms	245676 KB	Output is correct
12	Correct	12 ms	245676 KB	Output is correct
13	Correct	9 ms	245676 KB	Output is correct
14	Correct	9 ms	245676 KB	Output is correct
15	Correct	12 ms	245676 KB	Output is correct
16	Correct	8 ms	245676 KB	Output is correct
17	Correct	0 ms	245676 KB	Output is correct
18	Correct	12 ms	245676 KB	Output is correct
19	Correct	12 ms	245676 KB	Output is correct
20	Correct	10 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	2 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	8 ms	245676 KB	Output is correct
9	Correct	16 ms	245676 KB	Output is correct
10	Correct	17 ms	245676 KB	Output is correct
11	Correct	129 ms	245676 KB	Output is correct
12	Correct	70 ms	245676 KB	Output is correct
13	Correct	124 ms	245676 KB	Output is correct
14	Correct	239 ms	245676 KB	Output is correct
15	Correct	233 ms	245676 KB	Output is correct
16	Correct	505 ms	245676 KB	Output is correct
17	Correct	111 ms	245676 KB	Output is correct
18	Correct	195 ms	245676 KB	Output is correct
19	Correct	419 ms	245676 KB	Output is correct
20	Correct	288 ms	245676 KB	Output is correct

Subtask #4
60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	245676 KB	Output is correct
2	Correct	50 ms	245676 KB	Output is correct
3	Correct	101 ms	245676 KB	Output is correct
4	Correct	167 ms	245676 KB	Output is correct
5	Correct	241 ms	245676 KB	Output is correct
6	Correct	210 ms	245676 KB	Output is correct
7	Correct	198 ms	245676 KB	Output is correct
8	Correct	201 ms	245676 KB	Output is correct
9	Correct	220 ms	245676 KB	Output is correct
10	Correct	271 ms	245676 KB	Output is correct
11	Correct	242 ms	245676 KB	Output is correct
12	Correct	279 ms	245676 KB	Output is correct
13	Correct	407 ms	245676 KB	Output is correct
14	Correct	747 ms	245676 KB	Output is correct
15	Correct	888 ms	245676 KB	Output is correct
16	Correct	828 ms	245676 KB	Output is correct
17	Correct	821 ms	245676 KB	Output is correct
18	Correct	778 ms	245676 KB	Output is correct
19	Correct	759 ms	245676 KB	Output is correct
20	Correct	754 ms	245676 KB	Output is correct
21	Correct	736 ms	245676 KB	Output is correct
22	Correct	718 ms	245676 KB	Output is correct
23	Correct	700 ms	245676 KB	Output is correct
24	Correct	677 ms	245676 KB	Output is correct
25	Correct	290 ms	245676 KB	Output is correct

답안 #13746

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