oj.uz

Submission #282858

# Submission time Handle Problem Language Result Execution time Memory
282858 2020-08-25T05:11:23 Z arnold518 Abduction 2 (JOI17_abduction2) C++14
27 / 100
 292 ms 63484 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 288 ms 63352 KB Output is correct
13 Correct 292 ms 63352 KB Output is correct
14 Correct 291 ms 63352 KB Output is correct
15 Correct 289 ms 63380 KB Output is correct
16 Correct 284 ms 63352 KB Output is correct
17 Correct 250 ms 63352 KB Output is correct
18 Correct 266 ms 63444 KB Output is correct
19 Correct 250 ms 63352 KB Output is correct
20 Correct 241 ms 61432 KB Output is correct
21 Correct 260 ms 63352 KB Output is correct
22 Correct 250 ms 63480 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 288 ms 63352 KB Output is correct
13 Correct 292 ms 63352 KB Output is correct
14 Correct 291 ms 63352 KB Output is correct
15 Correct 289 ms 63380 KB Output is correct
16 Correct 284 ms 63352 KB Output is correct
17 Correct 250 ms 63352 KB Output is correct
18 Correct 266 ms 63444 KB Output is correct
19 Correct 250 ms 63352 KB Output is correct
20 Correct 241 ms 61432 KB Output is correct
21 Correct 260 ms 63352 KB Output is correct
22 Correct 250 ms 63480 KB Output is correct
23 Execution timed out 3 ms 640 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 63420 KB Output is correct
2 Correct 288 ms 63352 KB Output is correct
3 Correct 288 ms 63480 KB Output is correct
4 Correct 292 ms 63484 KB Output is correct
5 Correct 291 ms 63480 KB Output is correct
6 Correct 250 ms 63352 KB Output is correct
7 Correct 254 ms 63436 KB Output is correct
8 Correct 248 ms 63352 KB Output is correct
9 Correct 247 ms 62272 KB Output is correct
10 Correct 251 ms 63360 KB Output is correct
11 Correct 249 ms 63352 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 288 ms 63352 KB Output is correct
13 Correct 292 ms 63352 KB Output is correct
14 Correct 291 ms 63352 KB Output is correct
15 Correct 289 ms 63380 KB Output is correct
16 Correct 284 ms 63352 KB Output is correct
17 Correct 250 ms 63352 KB Output is correct
18 Correct 266 ms 63444 KB Output is correct
19 Correct 250 ms 63352 KB Output is correct
20 Correct 241 ms 61432 KB Output is correct
21 Correct 260 ms 63352 KB Output is correct
22 Correct 250 ms 63480 KB Output is correct
23 Execution timed out 3 ms 640 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -