oj.uz

Submission #26167

# Submission time Handle Problem Language Result Execution time Memory
26167 2017-06-28T07:56:12 Z 카제비(#1106, kajebiii) Abduction 2 (JOI17_abduction2) C++14
0 / 100
 196 ms 65336 KB 
#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][2] = Dy[i+1][p][2] + 1;
				else
					Dy[i][p][2] = 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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 65164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 65164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 65164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 196 ms 65336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 65164 KB Output isn't correct
2 Halted 0 ms 0 KB -