Submission #911252

#	Time	Username	Problem	Language	Result	Execution time	Memory
911252		Nonoze	Garden (JOI23_garden)	C++17	0 / 100	69 ms	17236 KiB

garden

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define sz(x) (int)(x.size())


int n, m, D;
vector<int> p, q;
vector<int> r, s;
vector<bool> xxx(5005, false), yyy(5005, false);

void build(multiset<int> &yy, set<int> qq) {
	for (auto u=qq.begin(); u!=qq.end(); u++) {
		auto v=++u;
		--u;
		if (v==qq.end()) {
			if (*u<D) yy.insert(D-(*u-*qq.begin()+1));
		} else {
			yy.insert(*v-*u-1);
		}
	}
}

int subtask5() {
	vector<pair<int, int>> x;
	set<int> y;
	for (int i=0; i<5005; i++) {
		int u=xxx[i];
		if (u) x.push_back({i, -1}), x.push_back({i+D, -1});
	}
	for (int i=0; i<5005; i++) {
		int u=yyy[i];
		if (u) y.insert(i);
	}
	multiset<int> yy;
	build(yy, y);
	int ans=D*D;
	for (int i=0; i<m; i++) x.push_back({r[i], i}), x.push_back({r[i]+D, i});
	sort(x.begin(), x.end());
	for (int a=0; a<D; a++) {
		auto lstx=x;
		auto lsty=y;
		auto lstyy=yy;
		int szy=0;
		{
			auto temp=yy.end();
			temp--;
			szy=D-*temp;
		}
		int empl=upper_bound(x.begin(), x.end(), make_pair(a+D, -2LL))-x.begin();
		while (empl==sz(x) || x[empl].first>=a+D) empl--;
		empl++;
		if (empl==sz(x) || x[empl].first==a+D) empl--;
		for (int i=0; i<m+1; i++) {
			auto value=s[x[empl].second];
			ans=min(ans, (x[empl].first-a+1)*szy);
			if (x[empl].second==-1) break;
			auto tempy=y.lower_bound(value);
			if (tempy==y.end() || *tempy!=value) {
				if (tempy==y.end()) {
					auto prec=y.end(), next=y.begin();
					prec--;
					int act=D-(*prec-*next+1);
					auto lb=yy.lower_bound(act);
					if (lb!=yy.end()) yy.erase(lb);
					yy.insert(D-(value-*next+1));
					yy.insert(value-*prec-1);
				} else if (tempy==y.begin()) {
					auto prec=y.begin(), next=y.end();
					next--;
					int act=D-(*next-*prec+1);
					auto lb=yy.lower_bound(act);
					if (lb!=yy.end()) yy.erase(lb);
					yy.insert(D-(*next-value+1));
					yy.insert(value-*prec-1);
				} else {
					auto next=tempy, prec=--tempy;
					int act=*next-*prec-1;
					auto lb=yy.lower_bound(act);
					if (lb!=yy.end()) yy.erase(lb);
					yy.insert(*next-value-1);
					yy.insert(value-*prec-1);
				}
				y.insert({value, -1});
			}
			{
				auto temp=yy.end();
				temp--;
				szy=D-*temp;
			}
			empl--;
		}
		x=lstx, y=lsty;
		yy=lstyy;
	}
	return ans;
}

int solve() {
	cin >> n >> m >> D;
	p.resize(n);
	q.resize(n);
	for (int i=0; i<n; i++) {
		cin >> p[i] >> q[i];
		xxx[p[i]]=true;
		yyy[q[i]]=true;
	}
	vector<pair<int, int>> temp;
	for (int i=0; i<m; i++) {
		int a, b; cin >> a >> b;
		if (xxx[a] || yyy[b]) continue;
		temp.push_back({a, b});
	}
	sort(temp.begin(), temp.end());
	m=sz(temp);
	r.clear(), s.clear();
	for (auto u: temp) r.push_back(u.first), s.push_back(u.second);
	return subtask5();
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << solve() << endl;
	return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25