oj.uz

Submission #6775

# Submission time Handle Problem Language Result Execution time Memory
6775 2014-07-06T07:29:38 Z woqja125 역사적 조사 (JOI14_historical) C++
100 / 100
 1400 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-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.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 8 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 0 ms 132112 KB Output is correct
10 Correct 4 ms 132112 KB Output is correct
11 Correct 8 ms 132112 KB Output is correct
12 Correct 8 ms 132112 KB Output is correct
13 Correct 8 ms 132112 KB Output is correct
14 Correct 8 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 8 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 4 ms 132112 KB Output is correct
8 Correct 4 ms 132244 KB Output is correct
9 Correct 32 ms 132376 KB Output is correct
10 Correct 40 ms 132112 KB Output is correct
11 Correct 168 ms 132112 KB Output is correct
12 Correct 124 ms 132112 KB Output is correct
13 Correct 428 ms 132376 KB Output is correct
14 Correct 536 ms 133960 KB Output is correct
15 Correct 476 ms 134752 KB Output is correct
16 Correct 296 ms 136732 KB Output is correct
17 Correct 180 ms 132112 KB Output is correct
18 Correct 288 ms 132112 KB Output is correct
19 Correct 336 ms 136732 KB Output is correct
20 Correct 216 ms 136732 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 132112 KB Output is correct
2 Correct 44 ms 132112 KB Output is correct
3 Correct 108 ms 132244 KB Output is correct
4 Correct 216 ms 132640 KB Output is correct
5 Correct 344 ms 132772 KB Output is correct
6 Correct 304 ms 132244 KB Output is correct
7 Correct 248 ms 132112 KB Output is correct
8 Correct 248 ms 132112 KB Output is correct
9 Correct 288 ms 132112 KB Output is correct
10 Correct 328 ms 132112 KB Output is correct
11 Correct 332 ms 132112 KB Output is correct
12 Correct 388 ms 132112 KB Output is correct
13 Correct 804 ms 132376 KB Output is correct
14 Correct 1244 ms 133564 KB Output is correct
15 Correct 1156 ms 134752 KB Output is correct
16 Correct 1216 ms 134092 KB Output is correct
17 Correct 1240 ms 133960 KB Output is correct
18 Correct 1236 ms 133696 KB Output is correct
19 Correct 1232 ms 133564 KB Output is correct
20 Correct 1284 ms 133432 KB Output is correct
21 Correct 1268 ms 133432 KB Output is correct
22 Correct 1260 ms 133300 KB Output is correct
23 Correct 1400 ms 133168 KB Output is correct
24 Correct 1272 ms 133168 KB Output is correct
25 Correct 344 ms 132112 KB Output is correct