Submission #13746

# Submission time Handle Problem Language Result Execution time Memory
13746 2015-03-30T15:00:27 Z gs13068 역사적 조사 (JOI14_historical) C++
100 / 100
888 ms 245676 KB
#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);
	}
}
# Verdict Execution time Memory 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 0 ms 245676 KB Output is correct
9 Correct 0 ms 245676 KB Output is correct
10 Correct 0 ms 245676 KB Output is correct
11 Correct 0 ms 245676 KB Output is correct
12 Correct 0 ms 245676 KB Output is correct
13 Correct 0 ms 245676 KB Output is correct
14 Correct 0 ms 245676 KB Output is correct
15 Correct 0 ms 245676 KB Output is correct
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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