Submission #885322

#	Time	Username	Problem	Language	Result	Execution time	Memory
885322		Mirali7	Colouring a rectangle (eJOI19_colouring)	C++17	100 / 100	464 ms	38424 KiB

colouring

//Picazo https://infoarena.ro/problema/picazo
#include <iostream>
#include <string>
#include <deque>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <fstream>
#include <stack>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <random>
#include <array>
#include <chrono>
#include <functional>
#include <numeric>
#include <complex>

using namespace std;

#define ll long long
#define ld long double
#define ull uint64_t
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pli pair<ll, int>
#define plli pair<pll, int>
#define pld pair<ld, ld>
#define fst first
#define snd second
#define pdi pair<ld, int>
#define pdd pair<double, double>

#define forn(i, n) for (int i = 1; i <= n; i++)
#define dforn(i, a, b) for (int i = a; i <= b; i++) 
#define rforn(i, n) for (int i = n; i >= 1; i--)
#define rdforn(i, a, b) for (int i = b; i >= a; i--)
#define sforn(i, a, b, s) for (int i = a; i <= b; i += s)
#define aforn(v, a) for (auto& v : a)
#define sz(a) ((int)a.size())

const int mod = 1e9 + 7;
const ld pi = acos(-1);
const ll N = 1e6;
const ll inf = 3e18;
const int iinf = 1 << 28;
const ld dinf = 1e9;
const double eps = 1e-12;

template <typename T>
struct lazy_tree {
	vector<T> t, add;
	int n = 1;
	lazy_tree(int sn) {
		while (n < sn) n <<= 1;
		t.resize(2 * n), add.resize(2 * n);
	}
	void push(int v, int l, int r) {
		if (add[v] == 0) return;
		t[v] += add[v];
		if (r - l > 1) add[2 * v] += add[v], add[2 * v + 1] += add[v];
		add[v] = 0;
	}
	void seg_set(int x, int l, int r, int ql, int qr, T v) {
		push(x, l, r);
		if (r <= ql || qr <= l) return;
		if (ql <= l && r <= qr) add[x] += v, push(x, l, r);
		else {
			int m = (l + r) >> 1;
			seg_set(2 * x, l, m, ql, qr, v);
			seg_set(2 * x + 1, m, r, ql, qr, v);
			t[x] = min(t[2 * x], t[2 * x + 1]);
		}
	}
	void seg_set(int ql, int qr, T x) { seg_set(1, 0, n, ql, qr, x); }
	T query(int l, int r, int x, int lx, int rx) {
		push(x, lx, rx);
		if (l >= rx || r <= lx) return inf;
		if (lx >= l && rx <= r) return t[x];
		int m = (lx + rx) >> 1;
		return min(query(l, r, 2 * x, lx, m), query(l, r, 2 * x + 1, m, rx));
	}
	T query(int l, int r) { return query(l, r, 1, 0, n); }
};

void solve() {
	int m, n;
	cin >> m >> n;
	vector<ll> lr_cost(m + n - 1), rl_cost(m + n - 1);
	dforn(i, 0, m + n - 2) cin >> lr_cost[i];
	reverse(lr_cost.begin(), lr_cost.end());
	dforn(i, 0, m + n - 2) cin >> rl_cost[i];
	vector<pii> seg(m + n - 1); pii p1 = { 0, 0 }, p2 = { 0, 0 };
	dforn(i, 0, m + n - 2) {
		seg[i] = { p1.snd - p1.fst, p2.snd - p2.fst };
		if (p1.fst != m - 1) p1.fst++; else p1.snd++;
		if (p2.snd != n - 1) p2.snd++; else p2.fst++;
	}
	int buf = -(*min_element(seg.begin(), seg.end())).fst;
	dforn(i, 0, m + n - 2) seg[i].fst += buf, seg[i].snd += buf;
	auto calc = [&](vector<int> v1, vector<int> v2) {
		v1.insert(v1.begin(), -1);
		int n = sz(v1);
		vector<vector<pii>> right(n);
		dforn(i, 0, sz(v2) - 1) {
			int lb = lower_bound(v1.begin(), v1.end(), seg[v2[i]].fst) - v1.begin(), rb = lower_bound(v1.begin(), v1.end(), seg[v2[i]].snd) - v1.begin();
			right[rb].push_back({ lb, rl_cost[v2[i]] });
		}
		lazy_tree<ll> Tr(n);
		forn(i, sz(v1) - 1) {
			ll val = Tr.query(0, i); Tr.seg_set(i, i + 1, val);
			Tr.seg_set(0, i, lr_cost[v1[i]]);
			aforn(v, right[i])
				Tr.seg_set(v.fst, i + 1, v.snd);
		}
		return Tr.query(0, n);
	};
	vector<int> v1, v2;
	sforn(i, 0, m + n - 2, 2) v1.push_back(i);
	dforn(i, 0, m + n - 2) if (seg[i].fst % 2 == 0) v2.push_back(i);
	ll ans = calc(v1, v2);
	v1.clear(), v2.clear();
	sforn(i, 1, m + n - 2, 2) v1.push_back(i);
	dforn(i, 0, m + n - 2) if (seg[i].fst % 2 == 1) v2.push_back(i);
	ans += calc(v1, v2);
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) solve();
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20