Submission #26187

#	Time	Username	Problem	Language	Result	Execution time	Memory
26187		khsoo01	Abduction 2 (JOI17_abduction2)	C++11	100 / 100	3393 ms	47504 KiB

abduction2

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tuple<ll,ll,ll> tp;
const ll N = 100005, L = 17, inf = 1e18;

ll h, w, q, a[N], inv[N], prv[L][N], nxt[L][N], vis[N];

priority_queue<tp> pq[N];
vector<pll> ord, st;

ll getprv (ll P, ll V) {
	if(a[P] > V) {
		for(ll i=P-1;i>=1;i--) {
			if(a[i] > V) return i;
		}
		return 0;
	}
	ll I = P;
	for(ll i=L;i--;) {
		if(a[prv[i][I]] <= V) I = prv[i][I];
	}
	return prv[0][I];
}

ll getnxt (ll P, ll V) {
	if(a[P] > V) {
		for(ll i=P+1;i<=h+w;i++) {
			if(a[i] > V) return i;
		}
		return 0;
	}
	ll I = P;
	for(ll i=L;i--;) {
		if(a[nxt[i][I]] <= V) I = nxt[i][I];
	}
	return nxt[0][I];
}

void solve () {
	ll P, Q, R = 0;
	scanf("%lld%lld",&P,&Q);
	Q += h;
	pq[inv[P]].push(tp(0, P, Q));
	pq[inv[Q]].push(tp(0, Q, P));
	for(ll i=1;i<=h+w;i++) vis[i] = 0;
	for(ll i=1;i<=h+w;i++) while(!pq[i].empty()) {
		ll A, B, C; tie(A, B, C) = pq[i].top(); pq[i].pop();
		if(vis[C] == i) continue;
		vis[C] = i;
		ll X = getprv(C, a[B]), Y = getnxt(C, a[B]);
		if(X && (X<=h)==(C<=h)) pq[inv[X]].push(tp(A+C-X, X, B));
		else R = max(R, A + C - (C<=h?1:h+1));
		if(Y && (Y<=h)==(C<=h)) pq[inv[Y]].push(tp(A+Y-C, Y, B));
		else R = max(R, A + (C<=h?h:h+w) - C);
	}
	printf("%lld\n",R);
}

int main()
{
	scanf("%lld%lld%lld",&h,&w,&q);
	ord.push_back({0, 0});
	for(ll i=1;i<=h+w;i++) {
		scanf("%lld",&a[i]);
		ord.push_back({a[i], i});
	}
	sort(ord.begin(), ord.end());
	for(ll i=1;i<=h+w;i++) {
		inv[ord[i].Y] = i;
	}
	st.push_back({inf, 0});
	for(ll i=1;i<=h+w;i++) {
		while(st.back().X <= a[i]) st.pop_back();
		prv[0][i] = st.back().Y;
		st.push_back({a[i], i});
	}
	st.clear();
	st.push_back({inf, 0});
	for(ll i=h+w;i>=1;i--) {
		while(st.back().X <= a[i]) st.pop_back();
		nxt[0][i] = st.back().Y;
		st.push_back({a[i], i});
	}
	a[0] = inf;
	for(ll k=1;k<L;k++) for(ll i=1;i<=h+w;i++) {
		nxt[k][i] = nxt[k-1][nxt[k-1][i]];
		prv[k][i] = prv[k-1][prv[k-1][i]];
	}
	while(q--) solve();
}

Compilation message (stderr)

abduction2.cpp: In function 'void solve()':
abduction2.cpp:45:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&P,&Q);
                         ^
abduction2.cpp: In function 'int main()':
abduction2.cpp:65:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&h,&w,&q);
                                ^
abduction2.cpp:68:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^

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