Submission #105721

#	Time	Username	Problem	Language	Result	Execution time	Memory
105721		Pro_ktmr	Abduction 2 (JOI17_abduction2)	C++14	100 / 100	4966 ms	129608 KiB

abduction2

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair

#define int long long

struct SegmentTree{
private:
	int N;
	vector<int> node;
public:
	void init(int n){
		N = 1;
		while(N < n) N *= 2;
		for(int i=0; i<2*N-1; i++) node.PB(0);
	}
	void update(int k, int x){
		k += N-1;
		node[k] = x;
		while(k > 0){
			k = (k-1)/2;
			node[k] = max(node[2*k+1], node[2*k+2]);
		}
	}
	int findL(int a, int b, int x, int k=0, int l=0, int r=-1){
		if(r == -1) r = N;
		if(r <= a || b <= l) return INT_MAX;
		if(r-l == 1){
			if(node[k] > x) return k-(N-1);
			else return INT_MAX;
		}
		if(a <= l && r <= b){
			if(node[2*k+1] > x) return findL(a, b, x, 2*k+1, l, (l+r)/2);
			if(node[2*k+2] > x) return findL(a, b, x, 2*k+2, (l+r)/2, r);
			return INT_MAX;
		}
		else{
			return min( findL(a, b, x, 2*k+1, l, (l+r)/2), findL(a, b, x, 2*k+2, (l+r)/2, r) );
		}
	}
	int findR(int a, int b, int x, int k=0, int l=0, int r=-1){
		if(r == -1) r = N;
		if(r <= a || b <= l) return INT_MIN;
		if(r-l == 1){
			if(node[k] > x) return k-(N-1);
			else return INT_MIN;
		}
		if(a <= l && r <= b){
			if(node[2*k+2] > x) return findR(a, b, x, 2*k+2, (l+r)/2, r);
			if(node[2*k+1] > x) return findR(a, b, x, 2*k+1, l, (l+r)/2);
			return INT_MIN;
		}
		else{
			return max( findR(a, b, x, 2*k+1, l, (l+r)/2), findR(a, b, x, 2*k+2, (l+r)/2, r) );
		}
	}
	void print(){
		for(int i=0; i<node.size(); i++) cout << node[i] << " ";
		cout << endl;
	}
};

int H,W,Q,A[50000],B[50000];
SegmentTree a,b;

map<pair<int,int>,int> dp;
/*
3
1 2
0
*/
int solve(int Y, int X, int moto){ //moto-10key
	if(moto == -1){
		int ans = 0;
		if(b.findR(0, X, A[Y]) != INT_MIN) ans = max(ans, solve(Y, b.findR(0, X, A[Y]), 2) +X-b.findR(0, X, A[Y]));
		else ans = max(ans, X);
		if(b.findL(X+1, W, A[Y]) != INT_MAX) ans = max(ans, solve(Y, b.findL(X+1, W, A[Y]), 1) +b.findL(X+1, W, A[Y])-X);
		else ans = max(ans, W-X-1);
		if(a.findR(0, Y, B[X]) != INT_MIN) ans = max(ans, solve(a.findR(0, Y, B[X]), X, 0) +Y-a.findR(0, Y, B[X]));
		else ans = max(ans, Y);
		if(a.findL(Y+1, H, B[X]) != INT_MAX) ans = max(ans, solve(a.findL(Y+1, H, B[X]), X, 3) +a.findL(Y+1, H, B[X])-Y);
		else ans = max(ans, H-Y-1);
		return ans;
	}
	if(dp.count({Y,X}) == 1) return dp[{Y,X}];
	int ans = 0;
	if(A[Y] > B[X]){
		if(b.findR(0, X, A[Y]) != INT_MIN) ans = max(ans, solve(Y, b.findR(0, X, A[Y]), 2) +X-b.findR(0, X, A[Y]));
		else ans = max(ans, X);
		if(b.findL(X+1, W, A[Y]) != INT_MAX) ans = max(ans, solve(Y, b.findL(X+1, W, A[Y]), 1) +b.findL(X+1, W, A[Y])-X);
		else ans = max(ans, W-X-1);
	}
	else{
		if(a.findR(0, Y, B[X]) != INT_MIN) ans = max(ans, solve(a.findR(0, Y, B[X]), X, 0) +Y-a.findR(0, Y, B[X]));
		else ans = max(ans, Y);
		if(a.findL(Y+1, H, B[X]) != INT_MAX) ans = max(ans, solve(a.findL(Y+1, H, B[X]), X, 3) +a.findL(Y+1, H, B[X])-Y);
		else ans = max(ans, H-Y-1);
	}
	//cout << Y << " " << X << " " << moto << " " << ans << endl;
	return dp[{Y,X}] = ans;
}

signed main(){
	cin >> H >> W >> Q;
	a.init(H);
	for(int i=0; i<H; i++){
		cin >> A[i];
		a.update(i, A[i]);
	}
	b.init(W);
	for(int i=0; i<W; i++){
		cin >> B[i];
		b.update(i, B[i]);
	}

	for(int i=0; i<Q; i++){
		int Y,X;
		cin >> Y >> X;
		Y--; X--;
		cout << solve(Y, X, -1) << endl;
	}

	return 0;
}

Compilation message (stderr)

abduction2.cpp: In member function 'void SegmentTree::print()':
abduction2.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<node.size(); i++) cout << node[i] << " ";
                ~^~~~~~~~~~~~

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