답안 #26168 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26168	2017-06-28T07:56:59 Z	카제비(#1106, kajebiii)	유괴 2 (JOI17_abduction2)	C++14	27 / 100	213 ms	65336 KB

abduction2

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 2e3 + 10;

int N, M, Q;
int Ns[MAX_N], Ms[MAX_N];
int Dy[MAX_N][MAX_N][4];
struct LN{
	int h, p, t;
	LN() {}
	LN(int hh, int pp, int tt) : h(hh), p(pp), t(tt) {}
	bool operator<(const LN &o) const{
		return h > o.h;
	}
};
vector<LN> Ls;
int main() {
	cin >> N >> M >> Q;
	REP(i, N) scanf("%d", &Ns[i]), Ls.push_back(LN(Ns[i], i, 0));
	REP(i, M) scanf("%d", &Ms[i]), Ls.push_back(LN(Ms[i], i, 1));

	assert(N <= 2000 && M <= 2000);

	sort(ALL(Ls));

	char Xs[9] = "1012", Ys[9] = "0121";
	for(LN &l : Ls) {
		int h = l.h, p = l.p, t = l.t;
		if(t == 0) {
			for(int i=1; i<M; i++) {
				if(h > Ms[i-1])
					Dy[p][i][0] = Dy[p][i-1][0] + 1;
				else
					Dy[p][i][0] = max(Dy[p][i-1][2], Dy[p][i-1][3]) + 1;
			}
			for(int i=M-2; i>=0; i--) {
				if(h > Ms[i+1])
					Dy[p][i][1] = Dy[p][i+1][1] + 1;
				else
					Dy[p][i][1] = max(Dy[p][i+1][2], Dy[p][i+1][3]) + 1;
			}
		} else {
			for(int i=1; i<N; i++) {
				if(h > Ns[i-1])
					Dy[i][p][2] = Dy[i-1][p][2] + 1;
				else
					Dy[i][p][2] = max(Dy[i-1][p][0], Dy[i-1][p][1]) + 1;
			}
			for(int i=N-2; i>=0; i--) {
				if(h > Ns[i+1])
					Dy[i][p][3] = Dy[i+1][p][3] + 1;
				else
					Dy[i][p][3] = max(Dy[i+1][p][0], Dy[i+1][p][1]) + 1;
			}
		}
	}
	while(Q--) {
		int x, y; scanf("%d%d", &x, &y); x--; y--;
		int ans = 0;
		for(int k=0; k<4; k++) ans = max(ans, Dy[x][y][k]);
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message

abduction2.cpp: In function 'int main()':
abduction2.cpp:39:7: warning: unused variable 'Xs' [-Wunused-variable]
  char Xs[9] = "1012", Ys[9] = "0121";
       ^
abduction2.cpp:39:23: warning: unused variable 'Ys' [-Wunused-variable]
  char Xs[9] = "1012", Ys[9] = "0121";
                       ^
abduction2.cpp:32:62: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  REP(i, N) scanf("%d", &Ns[i]), Ls.push_back(LN(Ns[i], i, 0));
                                                              ^
abduction2.cpp:33:62: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  REP(i, M) scanf("%d", &Ms[i]), Ls.push_back(LN(Ms[i], i, 1));
                                                              ^
abduction2.cpp:71:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y); x--; y--;
                                  ^

Subtask #1
13.0 / 13.0

#	결과	메모리	Grader output
1	Correct	65164 KB	Output is correct
2	Correct	65164 KB	Output is correct
3	Correct	65164 KB	Output is correct
4	Correct	65164 KB	Output is correct
5	Correct	65164 KB	Output is correct
6	Correct	65164 KB	Output is correct
7	Correct	65164 KB	Output is correct
8	Correct	65164 KB	Output is correct
9	Correct	65164 KB	Output is correct
10	Correct	65164 KB	Output is correct
11	Correct	65164 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	65164 KB	Output is correct
2	Correct	0 ms	65164 KB	Output is correct
3	Correct	0 ms	65164 KB	Output is correct
4	Correct	0 ms	65164 KB	Output is correct
5	Correct	0 ms	65164 KB	Output is correct
6	Correct	0 ms	65164 KB	Output is correct
7	Correct	0 ms	65164 KB	Output is correct
8	Correct	0 ms	65164 KB	Output is correct
9	Correct	0 ms	65164 KB	Output is correct
10	Correct	0 ms	65164 KB	Output is correct
11	Correct	0 ms	65164 KB	Output is correct
12	Correct	179 ms	65336 KB	Output is correct
13	Correct	196 ms	65336 KB	Output is correct
14	Correct	203 ms	65336 KB	Output is correct
15	Correct	196 ms	65336 KB	Output is correct
16	Correct	213 ms	65336 KB	Output is correct
17	Correct	149 ms	65336 KB	Output is correct
18	Correct	149 ms	65336 KB	Output is correct
19	Correct	156 ms	65336 KB	Output is correct
20	Correct	166 ms	65336 KB	Output is correct
21	Correct	173 ms	65336 KB	Output is correct
22	Correct	183 ms	65336 KB	Output is correct

Subtask #3
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	65164 KB	Output is correct
2	Correct	0 ms	65164 KB	Output is correct
3	Correct	0 ms	65164 KB	Output is correct
4	Correct	0 ms	65164 KB	Output is correct
5	Correct	0 ms	65164 KB	Output is correct
6	Correct	0 ms	65164 KB	Output is correct
7	Correct	0 ms	65164 KB	Output is correct
8	Correct	0 ms	65164 KB	Output is correct
9	Correct	0 ms	65164 KB	Output is correct
10	Correct	0 ms	65164 KB	Output is correct
11	Correct	0 ms	65164 KB	Output is correct
12	Correct	179 ms	65336 KB	Output is correct
13	Correct	196 ms	65336 KB	Output is correct
14	Correct	203 ms	65336 KB	Output is correct
15	Correct	196 ms	65336 KB	Output is correct
16	Correct	213 ms	65336 KB	Output is correct
17	Correct	149 ms	65336 KB	Output is correct
18	Correct	149 ms	65336 KB	Output is correct
19	Correct	156 ms	65336 KB	Output is correct
20	Correct	166 ms	65336 KB	Output is correct
21	Correct	173 ms	65336 KB	Output is correct
22	Correct	183 ms	65336 KB	Output is correct
23	Runtime error	0 ms	65336 KB	Execution killed because of forbidden syscall futex (202)
24	Halted	0 ms	0 KB	-

Subtask #4
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	206 ms	65336 KB	Output is correct
2	Correct	196 ms	65336 KB	Output is correct
3	Correct	193 ms	65336 KB	Output is correct
4	Correct	189 ms	65336 KB	Output is correct
5	Correct	193 ms	65336 KB	Output is correct
6	Correct	126 ms	65336 KB	Output is correct
7	Correct	146 ms	65336 KB	Output is correct
8	Correct	179 ms	65336 KB	Output is correct
9	Correct	163 ms	65336 KB	Output is correct
10	Correct	179 ms	65336 KB	Output is correct
11	Correct	156 ms	65336 KB	Output is correct

Subtask #5
0 / 56.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	65164 KB	Output is correct
2	Correct	0 ms	65164 KB	Output is correct
3	Correct	0 ms	65164 KB	Output is correct
4	Correct	0 ms	65164 KB	Output is correct
5	Correct	0 ms	65164 KB	Output is correct
6	Correct	0 ms	65164 KB	Output is correct
7	Correct	0 ms	65164 KB	Output is correct
8	Correct	0 ms	65164 KB	Output is correct
9	Correct	0 ms	65164 KB	Output is correct
10	Correct	0 ms	65164 KB	Output is correct
11	Correct	0 ms	65164 KB	Output is correct
12	Correct	179 ms	65336 KB	Output is correct
13	Correct	196 ms	65336 KB	Output is correct
14	Correct	203 ms	65336 KB	Output is correct
15	Correct	196 ms	65336 KB	Output is correct
16	Correct	213 ms	65336 KB	Output is correct
17	Correct	149 ms	65336 KB	Output is correct
18	Correct	149 ms	65336 KB	Output is correct
19	Correct	156 ms	65336 KB	Output is correct
20	Correct	166 ms	65336 KB	Output is correct
21	Correct	173 ms	65336 KB	Output is correct
22	Correct	183 ms	65336 KB	Output is correct
23	Runtime error	0 ms	65336 KB	Execution killed because of forbidden syscall futex (202)
24	Halted	0 ms	0 KB	-

답안 #26168

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 17.0

Subtask #4 4.0 / 4.0

Subtask #5 0 / 56.0

Subtask #1
13.0 / 13.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 17.0

Subtask #4
4.0 / 4.0

Subtask #5
0 / 56.0