CSAcademy: Round #76

つら。

ABC
はい。

D
あーもうめちゃくちゃだよ。
queueっぽいものが見えてから発想が転換できなかったのが敗因。
やっぱり実装力ないし、考察時に実装量を見積もるのも下手ですね。
面倒な問題たくさん解いて精進したほうが良さそう…

int N, M;
ll Y[MAX_N], X[MAX_N];
vector<ll> vec;
vector<pl> Q[MAX_N];
ll leftv[MAX_N], rightv[MAX_N];

int fd(ll v) {
	return lower_bound(all(vec), v) - vec.begin();
}

void pre(ll value[MAX_N]) {
	vec.clear();
	rep(i, 0, N) {
		vec.pb(X[i] - Y[i]);
		vec.pb(X[i] + Y[i]);
		vec.pb(X[i]);
	}
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	M = sz(vec);
	rep(i, 0, M) {
		Q[i].clear();
	}
	rep(i, 0, N) {
		int at1 = fd(X[i]);
		int at2 = fd(X[i] - Y[i]);
		Q[at1].pb(pl(X[i] - Y[i], i));
		Q[at2].pb(pl(X[i] - Y[i], i));
	}
	set<pl> que;
	rep(i, 0, M - 1) {
		rep(j, 0, sz(Q[i])) {
			pl x = Q[i][j];
			if(que.find(x) != que.end()) {
				que.erase(x);
			}
			else {
				que.insert(x);
			}
		}
		if(que.empty()) {
			value[i] = linf;
		}
		else value[i] = (*que.begin()).fst;
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N) {
		cin >> Y[i] >> X[i];
		X[i] *= -1;
	}
	pre(rightv);
	rep(i, 0, M - 1) {
		rightv[i] *= -1;
	}
	reverse(rightv, rightv + M);
	rep(i, 0, N) X[i] *= -1;
	pre(leftv);

	ll res = 0;
	// debug(vec);
	// debug(vl(leftv, leftv + M));
	// debug(vl(rightv, rightv + M));
	rep(i, 0, M - 1) {
		ll x1 = vec[i], x2 = vec[i + 1];
		ll l1 = x1 - leftv[i], l2 = x2 - leftv[i];
		ll r1 = rightv[i + 1] - x1, r2 = rightv[i + 1] - x2;
		// debug(i, x1, x2, l1, l2, r1, r2);
		ll X = x2 - x1;
		if(l1 < -linf / 2 && r1 < -linf / 2) continue;
		if(l1 >= r1) {
			ll l = l1 + X - 1;
			res += (l + l1) * X / 2;
		}
		else if(l2 <= r2) {
			ll r = r1 - (X - 1);
			res += (r + r1) * X / 2;
		}
		else {
			ll u = (r1 - l1) / 2;
			ll ul = r1 - u;
			ll ur = l1 + (u + 1);
			// debug(u, ul, ur);
			res += (u + 1) * (r1 + ul) / 2;
			res += (X - u - 1) * (l2 - 1 + ur) / 2;
		}
		// debug(res);
	}
	cout << res << "\n";
}

一応queueの解法でも通ったんで。でも上位陣の方々と比べると実装が遥かに複雑になってしまってるのが解ると思います。

E
mincutでしょって思ってたんですがmincutで通るらしいですね。Writerの想定解は違いますが。