Submission #911191

#	Time	Username	Problem	Language	Result	Execution time	Memory
911191		Nonoze	Garden (JOI23_garden)	C++17	6 / 100	974 ms	21328 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;


// int interval(set<pair<int, int>> &x, int empl) {
// 	auto it=x.lower_bound({empl, -1});
// 	int a=it->first, b;
// 	it--, b=it->first;
// 	return D-abs(a-b-1);
// }

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

int subtask5() {
	set<pair<int, int>> x, y;
	for (auto u: p) x.insert({u, -1}), x.insert({u+D, -1});
	for (auto u: q) y.insert({u, -1});
	multiset<int> xx, yy;
	build(xx, x);
	build(yy, y);
	int ans=D*D;
	for (int a=0; a<D; a++) {
		auto lstx=x, lsty=y;
		auto lstxx=xx, lstyy=yy;
		int szy=0;
		{
			auto temp=yy.end();
			temp--;
			szy=D-*temp;
		}
		for (int i=0; i<m; i++) x.insert({r[i], i}), x.insert({r[i]+D, i});
		auto it=x.upper_bound({a+D, -1});
		while (it==x.end() || it->first>=a+D) it--;
		if (it!=x.end()) it++;
		if (it==x.end() || it->first==a+D) it--;
		for (int i=0; i<m+1; i++) {
			ans=min(ans, (it->first-a+1)*szy);
			if (it->second==-1) break;
			auto tempy=y.lower_bound({s[it->second], -1});
			if (tempy->first!=s[it->second]) {
				if (tempy==y.begin()) {
					auto prec=y.begin(), next=y.end();
					next--;
					int act=D-(next->first-prec->first+1);
					yy.erase(yy.lower_bound(act));
					yy.insert(D-(next->first-s[it->second]+1));
					yy.insert(s[it->second]-prec->first-1);
				} else if (tempy==y.end()) {
					auto prec=y.end(), next=y.begin();
					prec--;
					int act=D-(prec->first-next->first+1);
					yy.erase(yy.lower_bound(act));
					yy.insert(D-(s[it->second]-next->first+1));
					yy.insert(s[it->second]-prec->first-1);
				} else {
					auto prec=--tempy; tempy++;
					auto next=tempy;
					int act=next->first-prec->first-1;
					yy.erase(yy.lower_bound(act));
					yy.insert(next->first-s[it->second]-1);
					yy.insert(s[it->second]-prec->first-1);
				}
				y.insert({s[it->second], -1});
			}
			{
				auto temp=yy.end();
				temp--;
				szy=D-*temp;
			}
			it--;
		}
		x=lstx, y=lsty;
		xx=lstxx, yy=lstyy;
	}
	return ans;
}


vector<bool> x(5000, false), y(5000, false);

int bruteforces(int empl) {
	if (empl==m) {
		int xmax=0, prec=0, prem=-1;
		for (int i=0; i<D; i++) {
			xmax=max(xmax, i-prec-1);
			if (x[i]) {
				prec=i;
				if (prem==-1) prem=i;
			}
		}
		xmax=D-xmax;
		xmax=min(xmax, prec-prem+1);
		int ymax=0;
		prec=0, prem=-1;
		for (int i=0; i<D; i++) {
			ymax=max(ymax, i-prec-1);
			if (y[i]) {
				prec=i;
				if (prem==-1) prem=i;
			}
		}
		ymax=D-ymax;
		ymax=min(ymax, prec-prem+1);
		return xmax*ymax;
	}
	bool xx=x[r[empl]], yy=y[s[empl]];
	x[r[empl]]=true;
	int ans=bruteforces(empl+1);
	x[r[empl]]=xx;
	y[s[empl]]=true;
	ans=min(ans, bruteforces(empl+1));
	y[s[empl]]=yy;
	return ans;
}

int subtask1() {
	for (auto u: p) x[u]=true;
	for (auto u: q) y[u]=true;
	return bruteforces(0);
}


int solve() {
	cin >> n >> m >> D;
	p.resize(n);
	q.resize(n);
	vector<bool> xxx(D, false), yyy(D, false);
	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);
	for (auto u: temp) r.push_back(u.first), s.push_back(u.second);
	//if (m<=8) return subtask1();
	return subtask5();
}


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

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