Submission #1169470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169470		Tob	Abduction 2 (JOI17_abduction2)	C++20	0 / 100	24 ms	656 KiB

abduction2

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int N = 50000, Q = 100, inf = 1e9;

int n, m, q;
int a[N], b[N], c[Q], d[Q], par[N], siz[N], bio[2*N];
int dis[2][2*N], civ[2*N][2];
bool br[2*N][2];
pii iv[N];
pii iva[N][2], ivb[N][2];

void smax(int& x, int y) {x = max(x, y);}

int find(int x) {return x == par[x] ? x : (par[x] = find(par[x]));}
void unite(int x, int y) {
	x = find(x); y = find(y);
	if (x == y) return;
	if (siz[x] < siz[y]) swap(x, y);
	par[y] = x;
	siz[x] += siz[y];
	if (iv[x].F < iv[y].F) iv[x].S = iv[y].S;
	else iv[x].F = iv[y].F;
}

int re(int x) {return (x<n ? x : x-n);}
void push(int x, int o) {
	if (dis[o][x] < -inf/2) return;
	if (!br[x][o]) {
		int y = civ[x][o];
		smax(dis[0][y], dis[o][x] + re(x) - re(civ[y][0]));
		smax(dis[1][y], dis[o][x] + re(civ[y][1]) - re(x));
	}
}

int main () {
	FIO;
	cin >> n >> m >> q;
	
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < m; i++) cin >> b[i];
	for (int i = 0; i < q; i++) cin >> c[i] >> d[i], c[i]--, d[i]--;
	
	vector <int> va, vb, v;
	for (int i = 0; i < n; i++) va.pb(i);
	for (int i = 0; i < m; i++) vb.pb(i);
	sort(all(va), [&](int x, int y){return a[x] < a[y];});
	sort(all(vb), [&](int x, int y){return b[x] < b[y];});
	
	for (int i = 0; i < n+m; i++) v.pb(i);
	sort(all(v), [&](int x, int y){return (x<n ? a[x] : b[x-n]) < (y<n ? a[y] : b[y-n]);});
	
	for (int j = 0; j < q; j++) {
		for (int i = 0; i <= m; i++) par[i] = i, siz[i] = 1, iv[i] = {i+n-1, i+n};
		for (int i = 0, l = 0; i < n; i++) {
			while (l < m && b[vb[l]] < a[va[i]]) {
				int x = vb[l++];
				unite(x, x+1);
			}
			for (int o = 0, de = 0; o < 2; o++, de++) if (d[j]+de >= 1 && d[j]+de < m) iva[va[i]][o] = iv[find(d[j]+de)];
		}
		
		for (int i = 0; i <= n; i++) par[i] = i, siz[i] = 1, iv[i] = {i-1, i};
		for (int i = 0, l = 0; i < m; i++) {
			while (l < n && a[va[l]] < b[vb[i]]) {
				int x = va[l++];
				unite(x, x+1);
			}
			for (int o = 0, de = 0; o < 2; o++, de++) if (c[j]+de >= 1 && c[j]+de < n) ivb[vb[i]][o] = iv[find(c[j]+de)];
		}
		
		int mx = 0;
		for (int o1 = 0, de1 = 0; o1 < 2; o1++, de1++) for (int o2 = 0, de2 = 0; o2 < 2; o2++, de2++) {
			if (c[j]+de2 < 1 || c[j]+de2 >= n || d[j]+de1 < 1 || d[j]+de1 >= m) continue;
			fill(bio, bio+n+m, 0);
			for (int i = 0; i < 2; i++) fill(dis[i], dis[i]+n+m, -inf);
			for (int i = 0; i < n; i++) civ[i][0] = iva[i][o1].F, civ[i][1] = iva[i][o1].S;
			for (int i = 0; i < m; i++) civ[i+n][0] = ivb[i][o2].F, civ[i+n][1] = ivb[i][o2].S;
			
			for (int i = 0; i < n+m; i++) br[i][0] = br[i][1] = 0;
			for (int i = 0; i < m; i++) {
				if (civ[i+n][0] == -1) br[i+n][0] = 1, civ[i+n][0] = 0;
				if (civ[i+n][1] == n) br[i+n][1] = 1, civ[i+n][1] = m-1;
			}
			for (int i = 0; i < n; i++) {
				if (civ[i][0] == n-1) br[i][0] = 1, civ[i][0] = n;
				if (civ[i][1] == n+m) br[i][1] = 1, civ[i][1] = n+m-1;
			}
			
			for (int i = 0; i < 2; i++) dis[i][c[j]] = abs(d[j] - re(civ[c[j]][i]));
			for (int i = 0; i < 2; i++) dis[i][d[j]+n] = abs(c[j] - re(civ[d[j]+n][i]));
			for (int i = 0; i < n+m; i++) push(v[i], 0), push(v[i], 1);
			for (int i = 0; i < n+m; i++) smax(mx, dis[0][i]), smax(mx, dis[1][i]);
		}
		cout << mx << "\n";
	}

	return 0;
}

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