oj.uz

답안 #128595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128595 2019-07-11T07:16:36 Z briansu 유괴 2 (JOI17_abduction2) C++14
0 / 100
 293 ms 860 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 293 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -