Submission #381424

#	Time	Username	Problem	Language	Result	Execution time	Memory
381424		pit4h	Abduction 2 (JOI17_abduction2)	C++14	0 / 100	60 ms	620 KiB

abduction2

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define cerr if(0)cerr
using namespace std;
using pii = pair<int, int>;
const int MAXH = 5e4+1;
int h, w, a[MAXH], b[MAXH];
int max_a, max_b;
int q;
list<pii> rows, colns;
list<pii>::iterator operator+(const list<pii>::iterator& iter, const int& increment) {
	auto res_iter = iter;
	if(increment >= 0) {
		for(int i=0; i<increment; ++i) {
			++res_iter;
		}
	}
	else {
		for(int i=0; i<abs(increment); ++i) {
			--res_iter;
		}
	}
	return res_iter;
}
inline void init() {
	rows.clear(), colns.clear();
	rows.push_back(mp(1e9+1, -1));
	for(int i=0; i<h; ++i) {
		rows.push_back(mp(a[i], i));
	}
	colns.push_back(mp(1e9+1, -1));
	for(int i=0; i<w; ++i) {
		colns.push_back(mp(b[i], i));
	}
}
bool lol=0;
list<pii>::iterator go_left(list<pii>& l, list<pii>::iterator x, int val) {
	auto it = x;	
	--it;
	while(true) {
		if((*it).st < val) {
			auto del = it;
			it--;
			l.erase(del);
		}
		else {
			break;
		}
	}
	return it;
}
list<pii>::iterator go_right(list<pii>& l, list<pii>::iterator x, int val) {
	auto it = x;
	++it;
	while(it != l.end()) {
		if((*it).st < val) {
			it = l.erase(it);
		}
		else {
			break;
		}
	}
	if(it == l.end()) {
		return l.begin();
	}
	return it;
}
int solve(list<pii>::iterator x, list<pii>::iterator y, bool turn) {
	cerr<<"solve "<<(*x).nd<<' '<<(*y).nd<<' '<<turn<<"  "<<(*x).st<<' '<<(*y).st<<'\n';
	if(!turn) {
		auto it = go_left(rows, x, (*y).st);	
		auto itr = go_right(rows, x, (*y).st);
		if((*it).nd == -1 && (*itr).nd == -1) {
			cerr<<' '<<max((*x).nd, h-(*x).nd-1)<<'\n';
			return max((*x).nd, h-(*x).nd-1);
		}
		if((*it).nd == -1) {
			int res1 =  (*x).nd;	
			int res2 = (*itr).nd - (*x).nd;
			res2 += solve(itr, y, !turn);
			cerr<<' '<<max(res1, res2)<<'\n';
			return max(res1, res2);
		}
		if((*itr).nd == -1) {
			int res1 = h-(*x).nd-1;
			int res2 = (*x).nd - (*it).nd;
			res2 += solve(it, y, !turn);
			cerr<<' '<<max(res1, res2)<<'\n';
			return max(res1, res2);
		}
		if(min((*it).st, (*itr).st) > max_b) {
			int res1 = (*x).nd - (*it).nd + max((*y).nd, w-(*y).nd-1); 
			int res2 = (*itr).nd - (*x).nd + max((*y).nd, w-(*y).nd-1);
			cerr<<' '<<max(res1, res2)<<'\n';
			return max(res1, res2);
		}
		if((*it).st < (*itr).st) {
			int res = (*x).nd - (*it).nd;
			res += solve(it, y, !turn);
			cerr<<' '<<res<<'\n';
			return res;
		}
		else {
			int res = (*itr).nd - (*x).nd;
			res += solve(itr, y, !turn);
			cerr<<' '<<res<<'\n';
			return res;
		}
	}
	else {
		auto it = go_left(colns, y, (*x).st);
		auto itr = go_right(colns, y, (*x).st);
		if((*it).nd == -1 && (*itr).nd == -1) {
			cerr<<' '<<max((*y).nd, w-(*y).nd-1)<<'\n';
			return max((*y).nd, w-(*y).nd-1);
		}
		if((*it).nd == -1) {
			int res1 =  (*y).nd;
			int res2 = (*itr).nd - (*y).nd;
			res2 +=  solve(x, itr, !turn);
			cerr<<' '<<max(res1, res2)<<'\n';
			return max(res1, res2);
		}
		if((*itr).nd == -1) {
			int res1 = w-(*y).nd-1;
			int res2 = (*y).nd - (*it).nd;
			res2 += solve(x, it, !turn);
			cerr<<' '<<max(res1, res2)<<'\n';
			return max(res1, res2);
		}
		if(min((*it).st, (*itr).st) > max_a) {
			int res1 = (*y).nd - (*it).nd + max((*x).nd, h-(*x).nd-1); 
			int res2 = (*itr).nd - (*y).nd + max((*x).nd, h-(*x).nd-1);
			cerr<<' '<<max(res1, res2)<<'\n';
			return max(res1, res2);
		}
		if((*it).st < (*itr).st) {
			int res = (*y).nd - (*it).nd;
			res += solve(x, it, !turn);
			cerr<<' '<<res<<'\n';
			return res;
		}
		else {
			int res = (*itr).nd - (*y).nd;
			res += solve(x, itr, !turn);
			cerr<<' '<<res<<'\n';
			return res;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>h>>w>>q;
	for(int i=0; i<h; ++i) {
		cin>>a[i];
		max_a = max(max_a, a[i]);
	}
	for(int i=0; i<w; ++i) {
		cin>>b[w-i-1];
		max_b = max(max_b, b[i]);
	}

	while(q--) {
		int s, t; cin>>s>>t;
		t = w-t+1;
		int res = 0;
		init();
		/// Left
		auto S = rows.begin()+s;
		auto T = colns.begin()+t;
		auto it = go_left(rows, S, (*T).st);
		if((*it).nd==-1) {
			res = max(res, (*S).nd);
		}
		else {
			int dist = (*S).nd - (*it).nd;
			res = max(res, dist+solve(it, T, 1));
		}
		init();
		/// Right
		S = rows.begin()+s;
		T = colns.begin()+t;
		it = go_right(rows, S, (*T).st);
		if((*it).nd==-1) {
			res = max(res, h-(*S).nd-1);
		}
		else {
			int dist = (*it).nd - (*S).nd;
			res = max(res, dist+solve(it, T, 1));
		}
		init();
		/// Up
		S = rows.begin()+s;
		T = colns.begin()+t;
		it = go_left(colns, T, (*S).st);
		if((*it).nd==-1) {
			res = max(res, (*T).nd);
		}
		else {
			int dist = (*T).nd - (*it).nd;
			res = max(res, dist+solve(S, it, 0));
		}
		init();
		/// Down
		S = rows.begin()+s;
		T = colns.begin()+t;
		it = go_right(colns, T, (*S).st);
		if((*it).nd==-1) {
			res = max(res, w-(*T).nd-1);
		}
		else {
			int dist = (*it).nd - (*T).nd;
			res = max(res, dist+solve(S, it, 0));
		}
		cout<<res<<'\n';
	}
}

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