Submission #219376

#	Time	Username	Problem	Language	Result	Execution time	Memory
219376		maruii	Treatment Project (JOI20_treatment)	C++14	4 / 100	118 ms	10472 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define ff first
#define ss second
#define eack emplace_back
#define all(x) (x).begin(), (x).end()

const ll INF = 1e18;
int N, M;
ll ans = INF;
map<int, vector<pair<pii, int>>> MP;

struct X {
	set<pil> S;
	void add(pil v) {
		auto it = S.lower_bound(pil(v.ff, 0));
		if (it != S.end() && it->ss <= v.ss) return;
		if (it == S.begin()) {
			if (it->ff == v.ff) S.erase(it);
			S.insert(v);
			return;
		}
		if (it->ff == v.ff) S.erase(it--);
		else --it;
		while (1) {
			if (it->ss >= v.ss) {
				if (it == S.begin()) {
					S.erase(it);
					break;
				}
				S.erase(it--);
			}
			else break;
		}
		S.insert(v);
	}

	void update(int s, int e, int v) {
		auto it = S.lower_bound(pil(s - 1, 0));
		if (it == S.end()) return;
		add(pil(e, it->ss + v));
	}
} a;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; ++i) {
		int t, l, r, c; cin >> t >> l >> r >> c;
		MP[t].eack(pii(l, r), c);
	}
	vector<pair<pii, pii>> vec;
	for (auto &i : MP) {
		int t = i.ff;
		for (auto j : i.ss) vec.eack(pii(t, j.ss), j.ff);
		vector<pair<pii, int>> v;
		for (auto j : vec) v.eack(pii(j.ss.ss == N ? N : j.ss.ss - t + j.ff.ff, j.ss.ff == 1 ? 1 : j.ss.ff + t - j.ff.ff), j.ff.ss);
		sort(all(v));
		a.S.clear();
		a.S.insert(pil(0, 0));
		for (auto i : v) if (i.ff.ss < i.ff.ff) a.update(i.ff.ss, i.ff.ff, i.ss);
		auto it = a.S.lower_bound(pil(N, 0));
		if (it != a.S.end()) ans = min(ans, it->ss);
	}
	if (ans == INF) ans = -1;
	cout << ans;
	return 0;
}

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