Submission #282858

#	Time	Username	Problem	Language	Result	Execution time	Memory
282858		arnold518	Abduction 2 (JOI17_abduction2)	C++14	27 / 100	292 ms	63484 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;

int N, M, Q;
int A[MAXN+10], B[MAXN+10];

int U[MAXN+10][MAXN+10], D[MAXN+10][MAXN+10], R[MAXN+10][MAXN+10], L[MAXN+10][MAXN+10];

int main()
{
	scanf("%d%d%d", &N, &M, &Q);

	vector<pii> V;
	for(int i=1; i<=N; i++) scanf("%d", &A[i]), V.push_back({A[i], i});
	for(int i=1; i<=M; i++) scanf("%d", &B[i]), V.push_back({B[i], i+N});

	sort(V.begin(), V.end(), greater<pii>());

	for(auto it : V)
	{
		int now=it.second;
		if(now>N)
		{
			now-=N;
			for(int i=1; i<N; i++)
			{
				if(A[i]>B[now])
				{
					if(now>1) U[i][now]=max(U[i][now], L[i][now-1]);
					if(now<M) U[i][now]=max(U[i][now], R[i][now]);
				}
				else if(i>1) U[i][now]=max(U[i][now], U[i-1][now]);
				U[i][now]++;
			}
			for(int i=N-1; i>=1; i--)
			{
				if(A[i+1]>B[now])
				{
					if(now>1) D[i][now]=max(D[i][now], L[i+1][now-1]);
					if(now<M) D[i][now]=max(D[i][now], R[i+1][now]);
				}
				else if(i<N-1) D[i][now]=max(D[i][now], D[i+1][now]);
				D[i][now]++;
			}
		}
		else
		{
			for(int i=1; i<M; i++)
			{
				if(B[i]>A[now])
				{
					if(now>1) L[now][i]=max(L[now][i], U[now-1][i]);
					if(now<N) L[now][i]=max(L[now][i], D[now][i]);
				}
				else if(i>1) L[now][i]=max(L[now][i], L[now][i-1]);
				L[now][i]++;
			}
			for(int i=M-1; i>=1; i--)
			{
				if(B[i+1]>A[now])
				{
					if(now>1) R[now][i]=max(R[now][i], U[now-1][i+1]);
					if(now<N) R[now][i]=max(R[now][i], D[now][i+1]);
				}
				else if(i<M-1) R[now][i]=max(R[now][i], R[now][i+1]);
				R[now][i]++;
			}
		}
	}

	while(Q--)
	{
		int y, x;
		scanf("%d%d", &y, &x);
		int ans=0;
		if(y>1) ans=max(ans, U[y-1][x]);
		if(x>1) ans=max(ans, L[y][x-1]);
		if(x<M) ans=max(ans, R[y][x]);
		if(y<N) ans=max(ans, D[y][x]);
		printf("%d\n", ans);
	}
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%d%d%d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:20:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]), V.push_back({A[i], i});
      |                          ~~~~~^~~~~~~~~~~~~
abduction2.cpp:21:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |  for(int i=1; i<=M; i++) scanf("%d", &B[i]), V.push_back({B[i], i+N});
      |                          ~~~~~^~~~~~~~~~~~~
abduction2.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |   scanf("%d%d", &y, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 0 / 17
• Subtask 4: 4 / 4
• Subtask 5: 0 / 56