Submission #943646

#	Time	Username	Problem	Language	Result	Execution time	Memory
943646		iliaaaaa	Garden (JOI23_garden)	C++17	30 / 100	3042 ms	5748 KiB

garden

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define All(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
#define pb push_back

const int N = 5e5 + 7, D = 5e3 + 7;
int n, m, d, cnt[D], hlp[D];
vector<int> vec[D];

struct Node {
	int ans, pre, suf;
	bool all;
}seg[D << 2];

Node merge(Node &a, Node &b) {
	Node res;
	res.all = (a.all && b.all);
	res.pre = max(a.pre, a.all * (a.pre + b.pre));
	res.suf = max(b.suf, b.all * (b.suf + a.suf));
	res.ans = max({a.ans, b.ans, a.suf + b.pre});
	return res;
}

void build(int id = 1, int st = 0, int en = d) {
	seg[id].pre = seg[id].suf = seg[id].ans = en - st;
	seg[id].all = 1;
	if (en - st == 1)
		return;
	int mid = (st + en) >> 1;
	build(id << 1, st, mid);
	build(id << 1 | 1, mid, en);
}

void upd(int p, int x, int id = 1, int st = 0, int en = d) {
	if (en - st == 1) {
		hlp[p] += x;
		if (hlp[p] < 0)
			assert(0);
		seg[id].ans = seg[id].pre = seg[id].suf = seg[id].all = (hlp[p] == 0);
		return;
	}
	int mid = (st + en) >> 1;
	if (p < mid)
		upd(p, x, id << 1, st, mid);
	else
		upd(p, x, id << 1 | 1, mid, en);
	seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}

int32_t main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> d;
	build();
	set<int> must;
	for (int i = 0; i < n; i++) {
		int p, q;
		cin >> p >> q;
		upd(q, 1);
		must.insert(p);
	}
	for (int i = 0; i < m; i++) {
		int r, s;
		cin >> r >> s;
		vec[r].pb(s);
		cnt[s]++;
	}
	set<int> rm;
	int ans = D * D;
	for (int i = 0; i < d; i++) {
		for (int j = 0; j < d; j++)
			upd(j, cnt[j]);
		rm = must;
		//cout << i << '\n';
		for (int j = 1; j <= d; j++) {
			int mod = (i + j - 1) % d;
			rm.erase(mod);
			for (int x: vec[mod])
				upd(x, -1);
			if (len(rm))
				continue;
			int tmp = d - max(seg[1].ans, seg[1].pre + seg[1].suf);
			//cout << i << ' ' << j << ' ' << tmp << '\n';
			ans = min(ans, tmp * j);
		}
	}
	cout << ans << '\n';
	return 0;
}

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