Submission #538196

#	Time	Username	Problem	Language	Result	Execution time	Memory
538196		fhvirus	Treatment Project (JOI20_treatment)	C++17	100 / 100	223 ms	33932 KiB

treatment

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#define debug(...) ((void)0)
#endif

struct Lisan: vector<int> {
	void done() { sort(begin(), end()); erase(unique(begin(), end()), end()); }
	int operator () (const int& v) const { return std::lower_bound(begin(), end(), v) - begin(); }
	int upper_bound (const int& v) const { return std::upper_bound(begin(), end(), v) - begin(); }
};

struct Treatment {
	int T, L, R, C, x, y;
	Treatment (const int& _T, const int& _L, const int& _R, const int& _C):
		T(_T), L(_L), R(_R), C(_C), x(L + T), y(L - T) {}
};

struct SegmentTree {
	int n; vector<vector<pair<int, int>>> val;
	SegmentTree (const int& _n): n(_n), val(4 << __lg(n)) {}
	void insert(int i, int l, int r, int p, pair<int, int> v) {
		if (l + 1 == r) {
			val[i].push_back(v);
			return;
		}
		int m = (l + r) / 2;
		if (p < m) insert(i * 2, l, m, p, v);
		else insert(i * 2 + 1, m, r, p, v);
	}
	void insert(int x, int y, int i) { insert(1, 0, n, x, pair<int, int>(y, i)); }
	void build(int i, int l, int r) {
		if (l + 1 == r) {
			sort(begin(val[i]), end(val[i]), greater<pair<int, int>>());
			return;
		}
		int m = (l + r) / 2;
		build(i * 2, l, m);
		build(i*2+1, m, r);
		val[i].reserve(val[i * 2].size() + val[i*2+1].size());
		merge(begin(val[i * 2]), end(val[i * 2]), begin(val[i*2+1]), end(val[i*2+1]), back_inserter(val[i]), greater<pair<int, int>>());
	}
	void build() { build(1, 0, n); }
	void collect(int i, int l, int r, int x, int y, vector<int>& ids) {
		debug(i, l, r, x, y, val[i]);
		if (x <= l) return;
		if (r <= x) {
			while (!val[i].empty()) {
				auto [yi, id] = val[i].back();
				if (yi <= y) {
					ids.emplace_back(id);
					val[i].pop_back();
				} else break;
			}
			return;
		}
		int m = (l + r) / 2;
		collect(i * 2, l, m, x, y, ids);
		if (m < x) collect(i * 2 + 1, m, r, x, y, ids);
	}
	void collect(int x, int y, vector<int>& ids) { collect(1, 0, n, x, y, ids); }
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, M;
	cin >> N >> M;

	vector<Treatment> ts;
	Lisan lisan;
	ts.reserve(M);
	lisan.reserve(M);
	for (int T, L, R, C, i = 0; i < M; ++i) {
		cin >> T >> L >> R >> C;
		ts.emplace_back(T, L, R, C);
		lisan.emplace_back(ts.back().x);
	}

	lisan.done();
	debug(lisan.size(), lisan);

	SegmentTree sgt(lisan.size());
	for (int i = 0; i < M; ++i) {
		const auto& [T, L, R, C, x, y] = ts[i];
		sgt.insert(lisan(x), y, i);
		debug(T, L, R, lisan(x), y, i);
	}
	sgt.build();

	vector<long long> dis(M, LLONG_MAX);
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
	for (int i = 0; i < M; ++i) {
		if (ts[i].L == 1) {
			dis[i] = ts[i].C;
			pq.emplace(dis[i], i);
		}
	}

	vector<int> vs;
	vs.reserve(M);
	while (!pq.empty()) {
		auto [d, u] = pq.top(); pq.pop();
		assert(d == dis[u]);

		int x = ts[u].R + ts[u].T + 1;
		int y = ts[u].R - ts[u].T + 1;
		debug(u, x, y);
		sgt.collect(lisan.upper_bound(x), y, vs);
		debug(vs);
		for (const int& v: vs) {
			if (d + ts[v].C < dis[v]) {
				dis[v] = d + ts[v].C;
				pq.emplace(dis[v], v);
			}
		}
		vs.clear();
	}

	long long ans = LLONG_MAX;
	for (int i = 0; i < M; ++i) {
		if (ts[i].R == N) {
			ans = min(ans, dis[i]);
		}
	}

	if (ans == LLONG_MAX) ans = -1;

	cout << ans << '\n';

	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61