Submission #6775

#	Time	Username	Problem	Language	Result	Execution time	Memory
6775		woqja125	역사적 조사 (JOI14_historical)	C++98	100 / 100	1400 ms	136732 KiB

historic

#include<stdio.h>
#include<map>
int imp[100501];
int impNum[100501];
int num[100501];
int dp[330][330];
int cnt[330][100001];
int chk[100001];
int main()
{
	int n, r, q, impC = 0;
	scanf("%d%d", &n, &q);
	for(int i=1; i<=n; i++) scanf("%d", &imp[i]);
	std::map<int, int> A;
	for(int i=1; i<=n; i++)
	{
		if(A.find(imp[i]) == A.end())
		{
			A.insert(std::make_pair(imp[i], ++impC));
			num[i] = impC;
			impNum[impC] = imp[i];
		}
		else
		{
			num[i] = A[imp[i]];
		}
	}
	for(r=1; r*r < n; r++);
	for(int i=1; i<=r; i++)
	{
		for(int j=1; j<=r; j++)
		{
			int t = i*r - r + j;
			if(num[t] == 0) break;
			for(int k=i; k<=r; k++) cnt[k][num[t]] ++;
		}
	}
	for(int i=1; i<=r; i++)
	{
		for(int j=i; j<=r; j++)
		{
			dp[i][j] = dp[i][j-1];
			for(int k=1; k<=r; k++)
			{
				int t = num[j*r - r + k];
				if(1ll*impNum[t]*(cnt[j][t]-cnt[i-1][t]) > 1ll*impNum[dp[i][j]]*(cnt[j][dp[i][j]]-cnt[i-1][dp[i][j]]))
					dp[i][j] = t;
			}
		}
	}
	for(int Q=1; Q<=q; Q++)
	{
		int s, f, a, b;
		scanf("%d%d", &a, &b);
		s = a; f = b;
		if(s==1) s=1;
		else
		{
			s-=2;
			s/=r;
			s+=2;
		}
		if(f==n) f = r;
		else
			f/=r;
		long long max = 0;
		if(s<=f)
		{
			max = 1ll*impNum[dp[s][f]]*(cnt[f][dp[s][f]] - cnt[s-1][dp[s][f]]);
			for(int i=a; i<=s*r-r; i++)
			{
				chk[num[i]] ++;
				if(1ll * imp[i] * (chk[num[i]] + cnt[f][num[i]] - cnt[s-1][num[i]]) > max)
					max = 1ll * imp[i] * (chk[num[i]] + cnt[f][num[i]] - cnt[s-1][num[i]] );
			}
			for(int i=f*r+1; i<=b; i++)
			{
				chk[num[i]] ++;
				if(1ll * imp[i] * (chk[num[i]] + cnt[f][num[i]] - cnt[s-1][num[i]]) > max)
					max = 1ll * imp[i] * (chk[num[i]] + cnt[f][num[i]] - cnt[s-1][num[i]] );
			}
			for(int i=a; i<=s*r-r; i++) chk[num[i]] = 0;
			for(int i=f*r-r; i<=b; i++) chk[num[i]] = 0;
		}
		else
		{
			for(int i=a; i<=b; i++)
			{
				chk[num[i]] ++;
				if(1ll * imp[i] * chk[num[i]] > max)
					max = 1ll * imp[i] * chk[num[i]];
			}
			for(int i=a; i<=b; i++) chk[num[i]] = 0;
		}
		printf("%lld\n", max);
	}
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60