oj.uz

Submission #469929

# Submission time Handle Problem Language Result Execution time Memory
469929 2021-09-02T10:53:54 Z luciocf 역사적 조사 (JOI14_historical) C++14
0 / 100
 13 ms 4620 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]] = 0;

			continue;
		//}

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

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

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

		for (int i = l; i <= (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 = 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 <= (b_l+1)*sq-1; i++)
			fq_aux[b[i]]--;

		for (int i = 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 296 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 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 440 KB Output is correct
7 Correct 5 ms 1868 KB Output is correct
8 Incorrect 13 ms 4620 KB Output isn't correct
9 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 -