제출 #911224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
911224		Nonoze	Garden (JOI23_garden)	C++17	15 / 100	74 ms	12880 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;

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() {
	set<pair<int, int>> x;
	set<int> y;
	for (auto u: p) x.insert({u, -1}), x.insert({u+D, -1});
	for (auto u: q) y.insert(u);
	multiset<int> yy;
	build(yy, y);
	int ans=D*D;
	for (int i=0; i<m; i++) x.insert({r[i], i}), x.insert({r[i]+D, i});
	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;
		}
		auto it=x.upper_bound({a+D, -1});
		while (it==x.end() || it->first>=a+D) it--;
		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]);
			if (tempy==y.end() || *tempy!=s[it->second]) {
				if (tempy==y.begin()) {
					auto prec=y.begin(), next=y.end();
					next--;
					int act=D-(*next-*prec+1);
					yy.erase(yy.lower_bound(act));
					yy.insert(D-(*next-s[it->second]+1));
					yy.insert(s[it->second]-*prec-1);
				} else if (tempy==y.end()) {
					auto prec=y.end(), next=y.begin();
					prec--;
					int act=D-(*prec-*next+1);
					yy.erase(yy.lower_bound(act));
					yy.insert(D-(s[it->second]-*next+1));
					yy.insert(s[it->second]-*prec-1);
				} else {
					auto prec=--tempy; tempy++;
					auto next=tempy;
					int act=*next-*prec-1;
					yy.erase(yy.lower_bound(act));
					yy.insert(*next-s[it->second]-1);
					yy.insert(s[it->second]-*prec-1);
				}
				y.insert({s[it->second], -1});
			}
			{
				auto temp=yy.end();
				temp--;
				szy=D-*temp;
			}
			it--;
		}
		x=lstx, y=lsty;
		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);
	r.clear(), s.clear();
	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: 15 / 15
• Subtask 2: 0 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25