Submission #537422

#	Time	Username	Problem	Language	Result	Execution time	Memory
537422		fhvirus	Treatment Project (JOI20_treatment)	C++17	0 / 100	78 ms	4900 KiB

treatment

#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...) LKJ("\033[1;32m[ " + string(#args) + " ]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void OI(I a, I b) { while (a != b) cerr << *a << " \n"[(a = next(a)) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

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

struct SGT {
	int n; vector<ll> val;
	SGT (int _n): n(_n), val(n * 4, INT_MAX) { }
	ll query(int i, int l, int r, int ql, int qr) {
		if (ql <= l and r <= qr) return val[i];
		int m = (l + r) / 2;
		ll ans = INT_MAX;
		if (ql < m) ans = min(ans, query(i * 2, l, m, ql, qr));
		if (m < qr) ans = min(ans, query(i*2+1, m, r, ql, qr));
		return ans;
	}
	void modify(int i, int l, int r, int p, ll v) {
		if (l + 1 == r) {
			val[i] = min(val[i], v);
			return;
		}
		int m = (l + r) / 2;
		if (p < m) modify(i * 2, l, m, p, v);
		else modify(i * 2 + 1, m, r, p, v);
		val[i] = min(val[i * 2], val[i * 2 + 1]);
	}
	ll query(int ql, int qr) { return query(1, 0, n, ql, qr); }
	void modify(int p, ll v) { modify(1, 0, n, p, v); }
};

void gg() {
	cout << -1 << '\n';
	exit(0);
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

	vector<tuple<int, int, int>> ts;
	Lisan lisan;
	ts.reserve(M);
	lisan.reserve(M + 1);
	lisan.pb(1);
	for (int T, L, R, C, i = 0; i < M; ++i) {
		cin >> T >> L >> R >> C;
		assert(T == 1);
		ts.pb(L, R, C);
		lisan.pb(R + 1);
	}

	sort(AI(ts));
	lisan.done();
	SGT sgt(lisan.size());

	sgt.modify(0, 0);

	for (auto& [l, r, c]: ts) {
		l = lisan(l);
		r = lisan.upper_bound(r);
		ll v = sgt.query(l, r);
		debug(l, r, c, v);
		sgt.modify(r, v + c);
	}

	if (lisan.back() != N + 1) gg();
	int pos = lisan.size() - 1;
	ll ans = sgt.query(pos, pos + 1);
	cout << ans << '\n';

	return 0;
}

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
treatment.cpp:82:3: note: in expansion of macro 'debug'
   82 |   debug(l, r, c, v);
      |   ^~~~~

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