Submission #61163

#	Time	Username	Problem	Language	Result	Execution time	Memory
61163		ainta	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	4181 ms	252144 KiB

abduction2

#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#define N_ 51000
#define SZ 65536
using namespace std;
int n, m, Q;
map<long long, long long>Map;
int X[N_], Y[N_];
long long Num(int x, int y, int dir) {
	return ((((long long)x << 16) + y) << 2) + dir;
}
struct Tree {
	int M[SZ+SZ];
	void Put(int a, int b) {
		a += SZ;
		M[a] = b;
		while (a != 1) {
			a >>= 1;
			M[a] = max(M[a * 2], M[a * 2 + 1]);
		}
	}
	int Before(int a, int g) {
		int b = SZ, e = a + SZ - 1, r = 0;
		while (b <= e) {
			if (M[e] > g) {
				r = e;
				break;
			}
			b = (b + 1) >> 1, e = (e - 1) >> 1;
		}
		if (r == 0)return r;
		while (r < SZ) {
			r *= 2;
			if (M[r + 1] > g)r++;
		}
		return r - SZ;
	}
	int Next(int a, int g) {
		int b = a + SZ + 1, e = SZ + SZ - 1, r = 1e9;
		while (b <= e) {
			if (M[b] > g) {
				r = b;
				break;
			}
			b = (b + 1) >> 1, e = (e - 1) >> 1;
		}
		if (r > 8e8)return r;
		while (r < SZ) {
			r *= 2;
			if (M[r] <= g)r++;
		}
		return r - SZ;
	}
}IT[2];
int Calc(int x, int y, int dir) {
	if (dir == 0)return x - 1;
	if (dir == 1)return n - x;
	if (dir == 2)return y - 1;
	if (dir == 3)return m - y;
}
long long Get(int x, int y, int dir) {
	long long tp = Num(x, y, dir);
	if (Map.count(tp))return Map[tp];
	if (x == 2 && y == 2 && dir == 1) {
		int ck = -1;
	}
	int t;
	if (dir == 0) t = IT[0].Before(x, Y[y]);
	if (dir == 1) t = IT[0].Next(x, Y[y]);
	if (dir == 2) t = IT[1].Before(y, X[x]);
	if (dir == 3) t = IT[1].Next(y, X[x]);
	long long Mn = 0;
	if (t<1 || t>1e6) {
		Map[tp] = Calc(x, y, dir);
		return Map[tp];
	}
	if (dir == 0 || dir == 1) {
		Mn = max(Mn, Get(t, y, 2) + abs(t - x));
		Mn = max(Mn, Get(t, y, 3) + abs(t - x));
	}
	else {
		Mn = max(Mn, Get(x, t, 0) + abs(t - y));
		Mn = max(Mn, Get(x, t, 1) + abs(t - y));
	}
	Map[tp] = Mn;
	return Mn;
}
int main() {
	int i, x, y;
	scanf("%d%d%d", &n, &m, &Q);
	for (i = 1; i <= n; i++) {
		scanf("%d", &X[i]);
		IT[0].Put(i, X[i]);
	}
	for (i = 1; i <= m; i++) {
		scanf("%d", &Y[i]);
		IT[1].Put(i, Y[i]);
	}
	while (Q--) {
		scanf("%d%d", &x, &y);
		long long Mn = 0;
		for (i = 0; i < 4; i++) {
			Mn = max(Mn, Get(x, y, i));
		}
		printf("%lld\n", Mn);
	}
}

Compilation message (stderr)

abduction2.cpp: In function 'long long int Get(int, int, int)':
abduction2.cpp:67:7: warning: unused variable 'ck' [-Wunused-variable]
   int ck = -1;
       ^~
abduction2.cpp: In function 'int Calc(int, int, int)':
abduction2.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
abduction2.cpp: In function 'int main()':
abduction2.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &X[i]);
   ~~~~~^~~~~~~~~~~~~
abduction2.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &Y[i]);
   ~~~~~^~~~~~~~~~~~~
abduction2.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp: In function 'long long int Get(int, int, int)':
abduction2.cpp:75:2: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (t<1 || t>1e6) {
  ^~

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