oj.uz

답안 #13891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13891 2015-04-11T00:58:35 Z comet 역사적 조사 (JOI14_historical) C++
15 / 100
 243 ms 120156 KB 
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
int N,Q,x[100010],c[100010][300],p[100010],s[100010],sz;
ll d[300][300];
int main(){
	scanf("%d%d",&N,&Q);
	for(int i=0;i<N;i++)scanf("%d",&x[i]),s[sz++]=x[i];
	sort(s,s+sz);
	sz=unique(s,s+sz)-s;
	for(int i=0;i<N;i++)x[i]=lower_bound(s,s+sz,x[i])-s;
	for(int i=0;i<N;i++){
		if(!(i&255)){
			for(int j=0;j<sz;j++)c[j][(i>>8)+1]=c[j][i>>8];
			for(int j=0;j<=(i>>8);j++)d[j][(i>>8)+1]=d[j][i>>8];
		}
		p[x[i]]++;
		c[x[i]][(i>>8)+1]++;
		for(int j=0;j<=(i>>8);j++)d[j][(i>>8)+1]=max(d[j][(i>>8)+1],1ll*s[x[i]]*(c[x[i]][(i>>8)+1]-c[x[i]][j]));
	}
	memset(p,0,sizeof(p));
	int S,E,l,r;
	ll ans;
	while(Q--){
		scanf("%d%d",&S,&E);
		S--;
		l=(S+255)>>8;
		r=E>>8;
		if(l>r){
			ans=0;
			for(int i=S;i<E;i++)p[x[i]]++;
			for(int i=S;i<E;i++){
				ans=max(ans,1ll*s[x[i]]*p[x[i]]);
				p[x[i]]--;
			}
		}
		else{
			ans=d[l][r];
			for(int i=S;i<(l<<8);i++)p[x[i]]++;
			for(int i=(r<<8);i<E;i++)p[x[i]]++;
			for(int i=S;i<(l<<8);i++)ans=max(ans,1ll*s[x[i]]*(p[x[i]]+c[x[i]][r]-c[x[i]][l])),p[x[i]]--;
			for(int i=(r<<8);i<E;i++)ans=max(ans,1ll*s[x[i]]*(p[x[i]]+c[x[i]][r]-c[x[i]][l])),p[x[i]]--;
		}
		printf("%lld\n",ans);
	}
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 120156 KB Output is correct
2 Correct 0 ms 120156 KB Output is correct
3 Correct 1 ms 120156 KB Output is correct
4 Correct 0 ms 120156 KB Output is correct
5 Correct 0 ms 120156 KB Output is correct
6 Correct 0 ms 120156 KB Output is correct
7 Correct 0 ms 120156 KB Output is correct
8 Correct 0 ms 120156 KB Output is correct
9 Correct 0 ms 120156 KB Output is correct
10 Correct 0 ms 120156 KB Output is correct
11 Correct 0 ms 120156 KB Output is correct
12 Correct 0 ms 120156 KB Output is correct
13 Correct 0 ms 120156 KB Output is correct
14 Correct 0 ms 120156 KB Output is correct
15 Correct 0 ms 120156 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 120156 KB Output is correct
2 Correct 0 ms 120156 KB Output is correct
3 Correct 0 ms 120156 KB Output is correct
4 Correct 0 ms 120156 KB Output is correct
5 Correct 0 ms 120156 KB Output is correct
6 Correct 2 ms 120156 KB Output is correct
7 Correct 0 ms 120156 KB Output is correct
8 Correct 8 ms 120156 KB Output is correct
9 Correct 12 ms 120156 KB Output is correct
10 Correct 21 ms 120156 KB Output is correct
11 Incorrect 147 ms 120156 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 120156 KB Output is correct
2 Correct 49 ms 120156 KB Output is correct
3 Correct 99 ms 120156 KB Output is correct
4 Correct 157 ms 120156 KB Output is correct
5 Correct 243 ms 120156 KB Output is correct
6 Correct 203 ms 120156 KB Output is correct
7 Correct 219 ms 120156 KB Output is correct
8 Incorrect 216 ms 120156 KB Output isn't correct
9 Halted 0 ms 0 KB -