Submission #414746

#	Time	Username	Problem	Language	Result	Execution time	Memory
414746		amoo_safar	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	4930 ms	326696 KiB

abduction2

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
#define int ll

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 5e4 + 10;
const ll Inf = 2242545357980376863LL;
const int Log = 16;

typedef pair<int, int> pii;
typedef pair<int, pii> T; // 0 -> R, 1 -> L, 2 -> D, 3 -> U;

int h, w;
int H[Log][N], W[Log][N];

vector<T> V;
bool Valid(T mv){
	pii pos = mv.S;
	int dir = mv.F;
	if(pos.F == h && dir == 2) return false;
	if(pos.F == 0 && dir == 3) return false;
	if(pos.S == w && dir == 0) return false;
	if(pos.S == 0 && dir == 1) return false;
	return true;
}
int Go(T mv){
	pii pos = mv.S;
	int dir = mv.F;
	if(dir == 0)
		return w - pos.S;
	if(dir == 1)
		return pos.S - 1;
	if(dir == 2)
		return h - pos.F;
	return pos.F - 1;
}


void Move(T mv){
	pii pos = mv.S;
	int dir = mv.F;
	
	int nw, v;
	if(dir == 0){
		nw = pos.S + 1;
		v = H[0][pos.F];
		for(int l = Log - 1; l >= 0; l--){
			if(nw + (1 << l) - 1 > w) continue;
			if(W[l][nw] < v){
				nw += (1 << l);
			}
		}
		if(nw == w + 1) return ;
		pos = {pos.F, nw};
		assert(W[0][nw] > v);
		V.pb({2, pos}); V.pb({3, pos});
	}
	if(dir == 1){
		nw = pos.S - 1;
		v = H[0][pos.F];
		for(int l = Log - 1; l >= 0; l--){
			if(nw - (1 << l) < 0) continue;
			if(W[l][nw - (1 << l) + 1] < v){
				nw -= (1 << l);
			}
		}
		if(nw == 0) return ;
		assert(W[0][nw] > v);
		pos = {pos.F, nw};
		V.pb({2, pos}); V.pb({3, pos});
	}
	if(dir == 2){
		nw = pos.F + 1;
		v = W[0][pos.S];
		for(int l = Log - 1; l >= 0; l--){
			if(nw + (1 << l) - 1 > h) continue;
			if(H[l][nw] < v){
				nw += (1 << l);
			}
		}
		if(nw == h + 1) return ;
		assert(H[0][nw] > v);
		pos = {nw, pos.S};
		V.pb({0, pos}); V.pb({1, pos});
	}
	if(dir == 3){
		nw = pos.F - 1;
		v = W[0][pos.S];
		for(int l = Log - 1; l >= 0; l--){
			if(nw - (1 << l) < 0) continue;
			if(H[l][nw - (1 << l) + 1] < v){
				nw -= (1 << l);
			}
		}
		if(nw == 0) return ;
		pos = {nw, pos.S};
		assert(H[0][nw] > v);

		V.pb({0, pos}); V.pb({1, pos});
	}
}

map<T, int> mp;
int dis(pii A, pii B){ return abs(A.F - B.F) + abs(A.S - B.S); }

int Solve(T nw){
	// cerr << "!! " << nw.F << ' ' << nw.S.F << ' ' << nw.S.S << '\n';
	if(!Valid(nw)) return -(3 * N);
	if(mp.count(nw))
		return mp[nw];

	V.clear();
	Move(nw);
	vector<T> V2 = V;
	int res = 0;

	// cerr << "----\n";
	// cerr << "$ (" << nw.F << ", (" << nw.S.F << ", " << nw.S.S << ")) :" << "\n";
	// for(auto x : V2)
	// 	cerr << "!! (" << x.F << ", (" << x.S.F << ", " << x.S.S << "))" << "\n";
	// cerr << "----\n";
	if(V2.empty())
		res = Go(nw);

	for(auto x : V2){
		// if(dis(nw.S, x.S) == 0){
		// 	cout << "##\n";
		// 	cout << nw.F << ' ' << nw.S.F << ' ' << nw.S.S << '\n';
		// 	cout << x.F << ' ' << x.S.F << ' ' << x.S.S << '\n';
		// }
		res = max(res, Solve(x) + dis(nw.S, x.S));
	}
	return mp[nw] = res;
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int q;
	cin >> h >> w >> q;
	for(int i = 1; i <= h; i++) cin >> H[0][i];
	for(int i = 1; i <= w; i++) cin >> W[0][i];
	for(int l = 0; l + 1 < Log; l++){
		int st = (1 << l);
		memcpy(H[l + 1], H[l], sizeof H[l]);
		for(int i = 1; i + st <= h; i++)
			H[l + 1][i] = max(H[l + 1][i], H[l][i + st]);

		memcpy(W[l + 1], W[l], sizeof W[l]);
		for(int i = 1; i + st <= w; i++)
			W[l + 1][i] = max(W[l + 1][i], W[l][i + st]);
	}
	int x, y;

	// Solve({0, {2, 2}});
	// for(auto [nw, rs] : mp)
	// 	cerr << "!! (" << nw.F << ", (" << nw.S.F << ", " << nw.S.S << ")) :" << rs << "\n";
	// exit(0);
	for(int i = 0; i < q; i++){
		int res = 0;
		cin >> x >> y;
		for(int d = 0; d < 4; d++)
			res = max(res, Solve({d, {x, y}}));
		cout << res << '\n';
	}
	return 0;
}

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