oj.uz

답안 #309602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
309602 2020-10-03T22:37:51 Z luciocf 유괴 2 (JOI17_abduction2) C++14
13 / 100
 5000 ms 5680 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e4+10;
const int maxl = 17;

int n, m;
int a[2][maxn];

map<int, int> dp[maxn][2];

struct SparseTable
{
	int tab[2][2][maxn][maxl];

	void build(void)
	{
		for (int i = 1; i <= n; i++)
		{
			if (i > 1) tab[0][0][i][0] = a[0][i-1];

			if (i < n) tab[0][1][i][0] = a[0][i+1];
		}

		for (int i = 1; i <= m; i++)
		{
			if (i > 1) tab[1][0][i][0] = a[1][i-1];

			if (i < m) tab[1][1][i][0] = a[1][i+1];
		}

		for (int j = 1; j < maxl; j++)
		{
			for (int i = 1; i <= n; i++)
			{
				if (i-(1<<j) > 0)
					tab[0][0][i][j] = max(tab[0][0][i][j-1], tab[0][0][i-(1<<(j-1))][j-1]);

				if (i+(1<<j) <= n)
					tab[0][1][i][j] = max(tab[0][1][i][j-1], tab[0][1][i+(1<<(j-1))][j-1]);
			}

			for (int i = 1; i <= m; i++)
			{
				if (i-(1<<j) > 0)
					tab[1][0][i][j] = max(tab[1][0][i][j-1], tab[1][0][i-(1<<(j-1))][j-1]);

				if (i+(1<<j) <= m)
					tab[1][1][i][j] = max(tab[1][1][i][j-1], tab[1][1][i+(1<<(j-1))][j-1]);
			}
		}
	}

	int get_l(int pos, int x, int q)
	{
		for (int i = maxl-1; i >= 0; i--)
			if (pos-(1<<i) > 0 && tab[q][0][pos][i] < x)
				pos -= (1<<i);

		return pos-1;
	}

	int get_r(int pos, int x, int q)
	{
		for (int i = maxl-1; i >= 0; i--)
			if (pos+(1<<i) <= (!q ? n : m) && tab[q][1][pos][i] < x)
				pos += (1<<i);

		return pos+1;
	}
} ST;

int solve(int i, int j, int q)
{
	if (dp[i][q].find(j) != dp[i][q].end()) return dp[i][q][j];

	if (!q)
	{
		int l = ST.get_l(j, a[0][i], 1), r = ST.get_r(j, a[0][i], 1);

		if (l == 0 && r == m+1) return max(j-1, m-j);
		if (l == 0) return (r-j + solve(i, r, 1));
		if (r == m+1) return (j-l + solve(i, l, 1));

		return max(r-j + solve(i, r, 1), j-l + solve(i, l, 1));
	}
	else
	{
		int l = ST.get_l(i, a[1][j], 0), r = ST.get_r(i, a[1][j], 0);

		if (l == 0 && r == n+1) return max(i-1, n-i);
		if (l == 0) return (r-i + solve(r, j, 0));
		if (r == n+1) return (i-l + solve(l, j, 0));

		return max(r-i + solve(r, j, 0), i-l + solve(l, j, 0));
	}
}

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

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

	for (int i = 1; i <= m; i++)
		scanf("%d", &a[1][i]);
	
	ST.build();

	while (q--)
	{
		int i, j;
		scanf("%d %d", &i, &j);

		printf("%d\n", max(solve(i, j, 0), solve(i, j, 1)));
	}
}

Compilation message

abduction2.cpp: In function 'int main()':
abduction2.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |   scanf("%d", &a[0][i]);
      |   ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |   scanf("%d", &a[1][i]);
      |   ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |   scanf("%d %d", &i, &j);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 3 ms 4992 KB Output is correct
9 Correct 3 ms 4992 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4992 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 3 ms 4992 KB Output is correct
9 Correct 3 ms 4992 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4992 KB Output is correct
12 Correct 4 ms 5632 KB Output is correct
13 Correct 5 ms 5632 KB Output is correct
14 Correct 5 ms 5632 KB Output is correct
15 Correct 5 ms 5632 KB Output is correct
16 Correct 5 ms 5632 KB Output is correct
17 Correct 5 ms 5632 KB Output is correct
18 Correct 5 ms 5632 KB Output is correct
19 Execution timed out 5051 ms 5632 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 3 ms 4992 KB Output is correct
9 Correct 3 ms 4992 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4992 KB Output is correct
12 Correct 4 ms 5632 KB Output is correct
13 Correct 5 ms 5632 KB Output is correct
14 Correct 5 ms 5632 KB Output is correct
15 Correct 5 ms 5632 KB Output is correct
16 Correct 5 ms 5632 KB Output is correct
17 Correct 5 ms 5632 KB Output is correct
18 Correct 5 ms 5632 KB Output is correct
19 Execution timed out 5051 ms 5632 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 5632 KB Output is correct
2 Correct 21 ms 5680 KB Output is correct
3 Correct 26 ms 5632 KB Output is correct
4 Correct 28 ms 5632 KB Output is correct
5 Correct 31 ms 5632 KB Output is correct
6 Correct 32 ms 5632 KB Output is correct
7 Correct 30 ms 5632 KB Output is correct
8 Execution timed out 5007 ms 5632 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 3 ms 4992 KB Output is correct
9 Correct 3 ms 4992 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4992 KB Output is correct
12 Correct 4 ms 5632 KB Output is correct
13 Correct 5 ms 5632 KB Output is correct
14 Correct 5 ms 5632 KB Output is correct
15 Correct 5 ms 5632 KB Output is correct
16 Correct 5 ms 5632 KB Output is correct
17 Correct 5 ms 5632 KB Output is correct
18 Correct 5 ms 5632 KB Output is correct
19 Execution timed out 5051 ms 5632 KB Time limit exceeded
20 Halted 0 ms 0 KB -