Submission #912763

#	Time	Username	Problem	Language	Result	Execution time	Memory
912763		Nonoze	Garden (JOI23_garden)	C++17	100 / 100	2870 ms	55692 KiB

garden

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

#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);

vector<int> prevv, nextt, used;
int intervalle=0;

int getprev(int x) {
	if (used[x]) prevv[x]=getprev(prevv[x]);
	return prevv[x];
}

int getnext(int x) {
	if (used[x]) nextt[x]=getnext(nextt[x]);
	return nextt[x];
}

void remove(int i) {
    int l = getprev(i);
    int r = getnext(i);
	used[i]=true;
	if (l==r) intervalle=D-1;
    intervalle = max(intervalle, (r-l+D)%D - 1);
    nextt[l] = r;
    prevv[r] = l;
}


bool can(int i) {
	return (i>=0 && i<2*D+5);
}

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

void build(vector<int> y) {
	prevv.resize(D+5);
	nextt.resize(D+5);
	used.resize(D+5, 0);
	if (sz(y)==1) intervalle=D-1;
	y.push_back(y[0]);
	for (int i=0; i<sz(y)-1; i++) {
		intervalle=max(intervalle, (y[i+1]-y[i]+D)%D-1);
		for (int j=y[i]+1; j<y[i+1]; j++) {
			nextt[j]=y[i+1];
			prevv[j]=y[i];
		}
		prevv[y[i+1]]=y[i];
		nextt[y[i]]=y[i+1];
	}
}


int subtask5() {
	vector<vector<int>> x(2*D+5);
	vector<vector<int>> correspond(D+5);
	vector<int> y;
	vector<bool> already=yyy;
	for (int i=0; i<5005; i++) {
		if (yyy[i]) y.push_back(i);
	}
	for (int i=0; i<m; i++) {
		x[r[i]].push_back(s[i]), x[r[i]+D].push_back(s[i]);
		correspond[s[i]].push_back(r[i]), correspond[s[i]].push_back(r[i]+D);
		if (!already[s[i]]) y.push_back(s[i]);
		already[s[i]]=true;
	}
	sort(y.begin(), y.end());
	build(y);
	int ans=D*D;

	for (auto &u: x) sort(u.begin(), u.end());
	for (auto &u: correspond) sort(u.begin(), u.end());
	auto baseprev=prevv;
	auto basenext=nextt;
	auto baseused=used;
	auto baseintervalle=intervalle;
	vector<int> emplacement(D+5, 0);
	for (int a=0; a<D; a++) {
		int szy=D-intervalle;
		vector<pair<int, int>> liste;
		int mxval=0;
		for (int i=0; i<D; i++) {
			if (xxx[i]) {
				int val=i;
				if (i<a) val+=D;
				mxval=max(mxval, val);
			}
			while (emplacement[i]+1<sz(correspond[i]) && correspond[i][emplacement[i]+1]<a+D) emplacement[i]++;
			if (emplacement[i]>=sz(correspond[i]) || correspond[i][emplacement[i]]<a) continue;
			liste.push_back({correspond[i][emplacement[i]], i});
		}
		vector<pair<int, int>> actions;
		sort(liste.begin(), liste.end());
		ans=min(ans, (mxval-a+1)*szy);
		for (int emplliste=0; emplliste<sz(liste); emplliste++) {
			remove(liste[emplliste].second);
			szy=D-intervalle;
			ans=min(ans, (max(liste[emplliste].first, mxval)-a+1)*szy);
		}
		prevv=baseprev;
		nextt=basenext;
		used=baseused;
		intervalle=baseintervalle;
	}
	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;
	map<pair<int, int>, bool> mp;
	for (int i=0; i<m; i++) {
		int a, b; cin >> a >> b;
		if (xxx[a] || yyy[b] || mp.count({a, b})) continue;
		temp.push_back({a, b});
		mp[{a, b}]=true;
	}
	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: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 25 / 25