제출 #128595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128595		briansu	유괴 2 (JOI17_abduction2)	C++14	0 / 100	293 ms	860 KiB

abduction2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define REP(i, n) for(int i = 0;i < n;i ++)
#define REP1(i, n) for(int i = 1;i <= n;i ++)
#define FILL(i, n) memset(i, n, sizeof(i))
#define X first
#define Y second
#define pb push_back
#define SZ(_a) ((int)(_a).size())
#define ALL(_a) (_a).begin(), (_a).end()
#ifdef brian
#define IOS()
template<typename T>void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...t>void _do(T &&x, t &&...X){cerr<<x<<", ";_do(X...);}
#define debug(...) {\
	fprintf(stderr, "%s - %d (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
	_do(__VA_ARGS__);\
}
#else
#define debug(...)
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#endif

const ll MAXn = 5e4 + 5;
const ll INF = ll(1e17);

#define R 0
#define C 1

ll r[MAXn], c[MAXn];
ll h, w, q;

set<ll> str, stc;

struct tg{
	ll x, tp, i;
};
queue<tg> que;

void init(){
	vector<tg> v;
	REP1(i, h)v.pb({r[i], R, i});
	REP1(i, w)v.pb({c[i], C, i});
	sort(ALL(v), [](tg &a, tg &b){return a.x < b.x;});
	while(SZ(que))que.pop();
	for(auto &p:v)que.push(p);
	str.clear(), stc.clear();
	REP1(i, h)str.insert(i);
	REP1(i, w)stc.insert(i);
}

ll mx = 0;

void gor(ll, ll, ll);
void goc(ll, ll, ll);

void gor(ll x,ll y, ll dis)// go along row x, changing y
{
	debug(x, y, dis);
	while(SZ(que) && que.front().x <= r[x])
	{
		auto t = que.front();que.pop();
		if(t.tp == R)str.erase(t.i);
		else stc.erase(t.i);
	}
	auto pit = stc.lower_bound(y);
	auto nit = pit;
	if(c[y] > r[x])nit ++;
	if(nit != stc.end())debug(*nit);
	if(pit != stc.begin())debug(*prev(pit));
	mx = max({mx, y - 1 + dis, w - y + dis});
	if(pit == stc.begin() && nit == stc.end())return;
	else if(nit == stc.end())goc(x, *prev(pit), dis + y - (*prev(pit)));
	else if(pit == stc.begin())goc(x, *nit, dis + (*nit) - y);
	else
	{
		ll a = *prev(pit);
		ll b = *nit;
		if(c[a] < c[b])goc(x, a, dis + y - a);
		else goc(x, b, dis + b - y);
	}
}

void goc(ll x,ll y, ll dis)// go along column y, changing x
{
	debug(x, y, dis);
	while(SZ(que) && que.front().x <= c[y])
	{
		auto t = que.front();que.pop();
		if(t.tp == R)str.erase(t.i);
		else stc.erase(t.i);
	}
	auto pit = str.lower_bound(x);
	auto nit = pit;
	if(r[x] > c[y])nit ++;
	mx = max({mx, x - 1 + dis, h - x + dis});
	if(pit == str.begin() && nit == str.end())return;
	else if(nit == str.end())gor(*prev(pit), y, dis + x - (*prev(pit)));
	else if(pit == str.begin())gor(*nit, y, dis + (*nit) - x);
	else
	{
		ll a = *prev(pit);
		ll b = *nit;
		if(c[a] < c[b])gor(a, y, dis + x - a);
		else gor(b, y, dis + b - x);
	}
}

int main(){
	IOS();
	cin>>h>>w>>q;
	REP1(i, h)cin>>r[i];
	REP1(i, w)cin>>c[i];	
	while(q--)
	{
		ll x, y;
		cin>>x>>y;
		debug(x, y);
		mx = 0;
		init();
		gor(x, y, 0);
		debug(mx);
		init();
		goc(x, y, 0);
		cout<<mx<<endl;
	}

}

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