Submission #21132

#	Time	Username	Problem	Language	Result	Execution time	Memory
21132		khsoo01	Abduction 2 (JOI17_abduction2)	C++11	44 / 100	5000 ms	15960 KiB

abduction2

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
ll h, w, q, a[100005], inv[100005];
ll vis[100005];

set<ll> s;
priority_queue<pair<ll, pair<ll, ll> > > pq[100005];
vector<pair<ll,ll> > ord;

void solve () {
	ll X, Y, ret = 0;
	scanf("%lld%lld",&X,&Y);
	Y += h;
	pq[inv[X]].push({0, {X, Y}});
	pq[inv[Y]].push({0, {Y, X}});
	for(int i=1;i<=h+w;i++) {
		s.insert(i);
		vis[i] = 0;
	}
	for(int i=0;i<h+w;i++) {
		while(!pq[i].empty()) {
			pair<ll,ll> st = pq[i].top().second;
			ll val = pq[i].top().first;
			pq[i].pop();
			if(vis[st.s] == i+1) continue;
			vis[st.s] = i+1;
			ret = max(ret, val);
			auto nxt = s.upper_bound(st.s);
			auto prv = s.lower_bound(st.s);
			bool f1 = (nxt != s.end() && (*nxt <= h) == (st.s <= h));
			bool f2 = (prv != s.begin() && (*(--prv) <= h) == (st.s <= h));
			if(!f1) ret = max(ret, val + (st.s <= h ? h : h + w) - st.s);
			else pq[inv[*nxt]].push({val + (*nxt) - st.s, {*nxt, st.f}});
			if(!f2) ret = max(ret, val + st.s - (st.s <= h ? 1 : h+1));
			else pq[inv[*prv]].push({val + st.s - (*prv), {*prv, st.f}});
		}
		s.erase(ord[i].second);
	}
	printf("%lld\n",ret);
}

int main()
{
	scanf("%lld%lld%lld",&h,&w,&q);
	for(int i=1;i<=h+w;i++) {
		scanf("%lld",&a[i]);
		ord.push_back({a[i], i});
	}
	sort(ord.begin(), ord.end());
	for(int i=0;i<h+w;i++) {
		inv[ord[i].second] = i;
	}
	while(q--) solve();
}

Compilation message (stderr)

abduction2.cpp: In function 'void solve()':
abduction2.cpp:15:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&X,&Y);
                         ^
abduction2.cpp: In function 'int main()':
abduction2.cpp:47: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:49: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: 0 / 56