oj.uz

Submission #13745

# Submission time Handle Problem Language Result Execution time Memory
13745 2015-03-30T14:56:20 Z gs13068 역사적 조사 (JOI14_historical) C++
5 / 100
 47 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];
		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

# 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

Subtask #2
0.0 / 10.0

# 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 4 ms 245676 KB Output is correct
5 Correct 6 ms 245676 KB Output is correct
6 Correct 6 ms 245676 KB Output is correct
7 Incorrect 8 ms 245676 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# 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 2 ms 245676 KB Output is correct
7 Correct 0 ms 245676 KB Output is correct
8 Incorrect 9 ms 245676 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 245676 KB Output is correct
2 Incorrect 47 ms 245676 KB Output isn't correct
3 Halted 0 ms 0 KB -