oj.uz

Submission #469925

# Submission time Handle Problem Language Result Execution time Memory
469925 2021-09-02T10:43:08 Z luciocf 역사적 조사 (JOI14_historical) C++14
0 / 100
 727 ms 55992 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5+10;
const int sq = 320;

int n;
int a[maxn], b[maxn];

int fq[maxn][sq], fq_aux[maxn];
ll best[sq][sq];

int soma(int l, int r, int v)
{
	if (l == 0) return fq[v][r];
	return fq[v][r] - fq[v][l-1];
}

int main(void)
{
	int q;
	scanf("%d %d", &n, &q);

	map<int, int> mp;

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);

		mp[a[i]] = 0;
	}

	int aux = 0;
	for (auto &x: mp)
		x.second = ++aux;

	for (int i = 1; i <= n; i++)
		b[i] = mp[a[i]];

	for (int i = 0; i*sq <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			fq[b[j]][i] = fq[b[j]][max(0, i-1)];

		for (int j = max(1, i*sq); j <= min(n, (i+1)*sq-1); j++)
			fq[b[j]][i]++;
	}

	for (int i = 0; i*sq <= n; i++)
	{
		for (int j = i; j*sq <= n; j++)
		{
			best[i][j] = best[i][max(0, j-1)];

			for (int k = max(1, j*sq); k <= min(n, (j+1)*sq-1); k++)
			{
				fq_aux[b[k]]++;

				best[i][j] = max(best[i][j], 1ll*a[k]*fq_aux[b[k]]);
			}
		}

		for (int j = 1; j <= n; j++)
			fq_aux[b[j]] = 0;
	}

	while (q--)
	{
		int l, r;
		scanf("%d %d", &l, &r);

		int b_l = l/sq, b_r = r/sq;
		ll ans = 0;

		if (b_l == b_r)
		{
			for (int i = l; i <= r; i++)
			{
				fq_aux[b[i]]++;

				ans = max(ans, 1ll*a[i]*fq_aux[b[i]]);
			}

			printf("%d\n", ans);

			for (int i = l; i <= r; i++)
				fq_aux[b[i]]--;

			continue;
		}

		if (b_l < b_r-1) ans = best[b_l+1][b_r-1];

		for (int i = l; i <= min(n, (b_l+1)*sq-1); i++)
			fq_aux[b[i]]++;

		for (int i = max(1, b_r*sq); i <= r; i++)
			fq_aux[b[i]]++;

		for (int i = l; i <= min(n, (b_l+1)*sq-1); i++)
			ans = max(ans, 1ll*a[i]*(fq_aux[b[i]] + (b_l < b_r-1 ? soma(b_l+1, b_r-1, b[i]) : 0)));

		for (int i = max(1, b_r*sq); i <= r; i++)
			ans = max(ans, 1ll*a[i]*(fq_aux[b[i]] + (b_l < b_r-1 ? soma(b_l+1, b_r-1, b[i]) : 0)));

		printf("%lld\n", ans);

		for (int i = l; i <= min(n, (b_l+1)*sq-1); i++)
			fq_aux[b[i]]--;

		for (int i = max(1, b_r*sq); i <= r; i++)
			fq_aux[b[i]]--;
	}
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:87:13: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
   87 |    printf("%d\n", ans);
      |            ~^     ~~~
      |             |     |
      |             int   ll {aka long long int}
      |            %lld
historic.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
historic.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
historic.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d %d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 5 ms 1868 KB Output is correct
8 Correct 14 ms 4560 KB Output is correct
9 Correct 39 ms 9796 KB Output is correct
10 Correct 88 ms 1504 KB Output is correct
11 Correct 405 ms 4096 KB Output is correct
12 Correct 338 ms 3072 KB Output is correct
13 Correct 450 ms 11688 KB Output is correct
14 Incorrect 727 ms 55992 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

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