Submission #566317

#	Time	Username	Problem	Language	Result	Execution time	Memory
566317		blue	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	1115 ms	14832 KiB

abduction2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using ll = long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using namespace std;

struct node
{
	int r, c, i;
};

const int mx = 50'000;

vi A(1+mx), B(1+mx);

const ll inf = 1'000'000'000'000'000LL;

int congestion(int i)
{
	if(i > 0)
		return A[i];
	else
		return B[-i];
}

struct inedge
{
	int i; //index
	int c; //congestion
	ll d; //dp
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int H, W, Q;
	cin >> H >> W >> Q;

	for(int i = 1; i <= H; i++)
		cin >> A[i];

	for(int j = 1; j <= W; j++)
		cin >> B[j];

	vi roads;
	for(int i = 1; i <= H; i++)
		roads.push_back(i);
	for(int j = 1; j <= W; j++)
		roads.push_back(-j);

	sort(roads.begin(), roads.end(), [] (int p, int q)
	{
		return congestion(p) < congestion(q);
	});

	A[0] = B[0] = 0;

	for(int q = 1; q <= Q; q++)
	{
		int S, T;
		cin >> S >> T;

		ll res = 0;

		// vll horiz_left(1+H, -inf), horiz_center(1+H, -inf), horiz_right(1+H, -inf); //dp
		// vll vert_up(1+W, -inf), vert_center(1+W, -inf), vert_down(1+W, -inf);

		ll ui = S-1, di = S+1, li = T-1, ri = T+1;

		vector<inedge> horiz_in[1+H], vert_in[1+W];

		horiz_in[S].push_back({T, 0, 0});
		vert_in[T].push_back({S, 0, 0});

		for(int f : roads)
		{
			if(f > 0) //road is horizontal
			{
				ll hl = -inf, hc = -inf, hr = -inf;

				int z = f;

				while(li >= 1 && B[li] < A[z])
					li--;

				while(ri <= W && B[ri] < A[z])
					ri++;

				for(inedge x : horiz_in[z])
				{
					if(x.c >= A[z]) continue;

					if(x.i <= li || ri <= x.i) continue;

					if(A[z] < B[T])
						hc = max(hc, x.d + abs(T - x.i));

					if(li != 0 && (x.i <= T || A[z] > B[T]))
					{
						hl = max(hl, x.d + abs(li - x.i));
					}
					else if(li == 0 && (x.i <= T || A[z] > B[T]))
						res = max(res, x.d + abs(x.i - 1));

					if(ri != W+1 && (x.i >= T || A[z] > B[T]))
					{
						hr = max(hr, x.d + abs(ri - x.i));
					}
					else if(ri == W+1 && (x.i >= T || A[z] > B[T]))
						res = max(res, x.d + abs(x.i - W));
				}

				if(A[z] < B[T])
				{
					vert_in[T].push_back({z, A[z], hc});
				}

				if(li != 0)
					vert_in[li].push_back({z, A[z], hl});

				if(ri != W+1)
					vert_in[ri].push_back({z, A[z], hr});
			}
			else
			{
				ll vu = -inf, vc = -inf, vd = -inf;

				int z = -f;

				while(ui >= 1 && A[ui] < B[z])
					ui--;

				while(di <= H && A[di] < B[z])
					di++;

				for(inedge x : vert_in[z])
				{
					if(x.c >= B[z]) continue;

					if(x.i <= ui || di <= x.i) continue;

					if(B[z] < A[S])
						vc = max(vc, x.d + abs(S - x.i));

					if(ui != 0 && (x.i <= S || B[z] > A[S]))
					{
						vu = max(vu, x.d + abs(ui - x.i));
					}
					else if(ui == 0 && (x.i <= S || B[z] > A[S]))
						res = max(res, x.d + abs(1 - x.i));

					if(di != H+1 && (x.i >= S || B[z] > A[S]))
					{
						vd = max(vd, x.d + abs(di - x.i));
					}
					else if(di == H+1 && (x.i >= S || B[z] > A[S]))
						res = max(res, x.d + abs(H - x.i));
				}

				if(B[z] < A[S])
				{
					horiz_in[S].push_back({z, B[z], vc});
				}

				if(ui != 0)
					horiz_in[ui].push_back({z, B[z], vu});

				if(di != H+1)
					horiz_in[di].push_back({z, B[z], vd});
			}
		}

		cout << res << '\n';
	}
}

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