oj.uz

Submission #6777

# Submission time Handle Problem Language Result Execution time Memory
6777 2014-07-06T10:59:11 Z woqja125 역사적 조사 (JOI14_historical) C++
100 / 100
 1164 ms 136732 KB 
#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+1; 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132112 KB Output is correct
2 Correct 0 ms 132112 KB Output is correct
3 Correct 0 ms 132112 KB Output is correct
4 Correct 0 ms 132112 KB Output is correct
5 Correct 0 ms 132112 KB Output is correct
6 Correct 0 ms 132112 KB Output is correct
7 Correct 0 ms 132112 KB Output is correct
8 Correct 0 ms 132112 KB Output is correct
9 Correct 0 ms 132112 KB Output is correct
10 Correct 0 ms 132112 KB Output is correct
11 Correct 0 ms 132112 KB Output is correct
12 Correct 0 ms 132112 KB Output is correct
13 Correct 0 ms 132112 KB Output is correct
14 Correct 0 ms 132112 KB Output is correct
15 Correct 0 ms 132112 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132112 KB Output is correct
2 Correct 0 ms 132112 KB Output is correct
3 Correct 0 ms 132112 KB Output is correct
4 Correct 0 ms 132112 KB Output is correct
5 Correct 4 ms 132112 KB Output is correct
6 Correct 0 ms 132112 KB Output is correct
7 Correct 4 ms 132112 KB Output is correct
8 Correct 4 ms 132112 KB Output is correct
9 Correct 4 ms 132112 KB Output is correct
10 Correct 8 ms 132112 KB Output is correct
11 Correct 4 ms 132112 KB Output is correct
12 Correct 8 ms 132112 KB Output is correct
13 Correct 0 ms 132112 KB Output is correct
14 Correct 4 ms 132112 KB Output is correct
15 Correct 8 ms 132112 KB Output is correct
16 Correct 4 ms 132112 KB Output is correct
17 Correct 0 ms 132112 KB Output is correct
18 Correct 4 ms 132112 KB Output is correct
19 Correct 8 ms 132112 KB Output is correct
20 Correct 8 ms 132112 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132112 KB Output is correct
2 Correct 0 ms 132112 KB Output is correct
3 Correct 0 ms 132112 KB Output is correct
4 Correct 0 ms 132112 KB Output is correct
5 Correct 0 ms 132112 KB Output is correct
6 Correct 0 ms 132112 KB Output is correct
7 Correct 0 ms 132112 KB Output is correct
8 Correct 12 ms 132244 KB Output is correct
9 Correct 32 ms 132376 KB Output is correct
10 Correct 32 ms 132112 KB Output is correct
11 Correct 160 ms 132112 KB Output is correct
12 Correct 128 ms 132112 KB Output is correct
13 Correct 436 ms 132376 KB Output is correct
14 Correct 568 ms 133960 KB Output is correct
15 Correct 480 ms 134752 KB Output is correct
16 Correct 272 ms 136732 KB Output is correct
17 Correct 176 ms 132112 KB Output is correct
18 Correct 252 ms 132112 KB Output is correct
19 Correct 328 ms 136732 KB Output is correct
20 Correct 204 ms 136732 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 132112 KB Output is correct
2 Correct 40 ms 132112 KB Output is correct
3 Correct 88 ms 132244 KB Output is correct
4 Correct 188 ms 132640 KB Output is correct
5 Correct 316 ms 132772 KB Output is correct
6 Correct 284 ms 132244 KB Output is correct
7 Correct 212 ms 132112 KB Output is correct
8 Correct 236 ms 132112 KB Output is correct
9 Correct 252 ms 132112 KB Output is correct
10 Correct 304 ms 132112 KB Output is correct
11 Correct 308 ms 132112 KB Output is correct
12 Correct 348 ms 132112 KB Output is correct
13 Correct 720 ms 132376 KB Output is correct
14 Correct 1124 ms 133564 KB Output is correct
15 Correct 1016 ms 134752 KB Output is correct
16 Correct 1088 ms 134092 KB Output is correct
17 Correct 1108 ms 133960 KB Output is correct
18 Correct 1164 ms 133696 KB Output is correct
19 Correct 1100 ms 133564 KB Output is correct
20 Correct 1136 ms 133432 KB Output is correct
21 Correct 1140 ms 133432 KB Output is correct
22 Correct 1132 ms 133300 KB Output is correct
23 Correct 1144 ms 133168 KB Output is correct
24 Correct 1100 ms 133168 KB Output is correct
25 Correct 320 ms 132112 KB Output is correct