Submission #35369546

---

Source Code Expand

#include <bits/stdc++.h>
#define R(i, a, b) for (auto i = (a); i < (b); ++i)
#define L(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define N(a) int((a).size())
#define V(a) (a).begin(), (a).end()
#define P make_pair
#define spc << ' '
#define ntr << '\n'
#define X(a) cerr << #a << " = " << a
#define T() cerr << "TIME = " << double(clock() - T0) / CLOCKS_PER_SEC
using namespace std;
using i64 = long long;
clock_t T0 = clock();
template<typename tp>
ostream &operator<<(ostream &ost, const pair<tp, tp> &a) {
	for (tp i = a.first; i != a.second; ++i) ost << setw(3) << *i;
	return ost;
}
constexpr int xN = 300000 + 7, xX = 1000000 + 7;
int N, M;
int mx, X[xN], D[xN];
template<typename tp>
struct iarr {
	tp a[xX * 2], *b = a + xX;
	tp &operator[](int i) {
		return b[i];
	}
	const tp operator[](int i) const {
		return b[i];
	}
};
template<typename tp>
ostream &operator<<(ostream &ost, const iarr<tp> &a) {
	R(i, -mx, mx + 1) ost << setw(3) << a[i];
	return ost;
}
iarr<bool> zer;
iarr<int> te, tur;
int fr(int u) {
	return u == te[u] ? u : te[u] = fr(te[u]);
}
struct seg {
	int l, r, p;
	int size() const {
		return r + 1 - l;
	}
	bool inl(int i) {
		return l <= i and i <= r;
	}
	bool inp(int i) {
		return p <= i and i < p + size();
	}
	int fp(int i) {
		assert(inl(i));
		return p + (i - l);
	}
	int fl(int i) {
		assert(inp(i));
		return l + (i - p);
	}
	void check_zero(int i, int m) {
		if (inl(m)) {
			zer[fp(m)] = zer[-fp(m)] = true;
			tur[fp(m)] = tur[-fp(m)] = i;
		}
	}
	seg shift(int i) {
		int m = D[i];
		if (m < l) return {l - m, r - m, p};
		if (m * 2 <= l + r) {
			R(i, 0, m - l) {
				te[fr(fp(l + i))] = fr(-fp(m + m - l - i));
				te[fr(-fp(l + i))] = fr(fp(m + m - l - i));
			}
			check_zero(i, m);
			if (1 > r - m) return {-1, -1, -1};
			return {1, r - m, fp(m + 1)};
		}
		if (m > r) return {m - r, m - l, -fp(r)};
		R(i, 0, r - m) {
			te[fr(fp(r - i))] = fr(-fp(m + m - r + i));
			te[fr(-fp(r - i))] = fr(fp(m + m - r + i));
		}
		check_zero(i, m);
		if (1 > m - l) return {-1, -1, -1};
		return {1, m - l, -fp(m - 1)};
	}
	int pos(int i) {
		if (inp(i)) return fl(i);
		return -fl(-i);
	}
};
int main() {
	cerr << fixed << setprecision(3);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N >> M;
	R(i, 0, N) cin >> X[i];
	R(i, 0, M) cin >> D[i];
	mx = *max_element(X, X + N);
	R(i, -mx, mx + 1) te[i] = i;
	seg s = {1, mx, 1};
	R(i, 0, M) if (!~(s = s.shift(i)).l) break;
	R(i, 0, N) {
		int u = fr(X[i]);
		if (zer[u]) cout << "Yes" spc << tur[u] + 1 ntr;
		else cout << "No" spc << s.pos(u) ntr;
	}
}

Submission Info

Judge Result