Submission #219357

#	Time	Username	Problem	Language	Result	Execution time	Memory
219357		maruii	Treatment Project (JOI20_treatment)	C++14	4 / 100	161 ms	14060 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, b;

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(r, l), c);
	}
	for (auto &i : MP) {
		int t = i.ff;
		sort(all(i.ss));
		for (auto it = a.S.begin(); it != a.S.end();) {
			if (it->ff > t) break;
			a.S.erase(it++);
		}
		for (auto it = b.S.begin(); it != b.S.end();) {
			if (it->ff > t) break;
			b.S.erase(it++);
		}
		a.S.insert(pil(t, 0));
		for (auto &j : i.ss) {
			a.update(t + j.ff.ss, t + j.ff.ff, j.ss);
			j.ff.ff = N + 1 - j.ff.ff;
			j.ff.ss = N + 1 - j.ff.ss;
			swap(j.ff.ff, j.ff.ss);
		}
		sort(all(i.ss));
		b.S.insert(pil(t, 0));
		for (auto &j : i.ss) b.update(t + j.ff.ss, t + j.ff.ff, j.ss);
		if (a.S.rbegin()->ff - t >= N - (b.S.rbegin()->ff - t)) {
			auto it = a.S.lower_bound(pil(N - (b.S.rbegin()->ff - t) + t, 0));
			ans = min(b.S.rbegin()->ss + it->ss, ans);
		}
	}
	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