Submission #423815

#	Time	Username	Problem	Language	Result	Execution time	Memory
423815		pavement	Treatment Project (JOI20_treatment)	C++17	4 / 100	131 ms	16744 KiB

treatment

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<iii, null_type, greater<iii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, M, out = 1e17, T[100005], L[100005], R[100005], C[100005], dp[100005];
iiii K[100005];

struct node {
	node *left, *right;
	int S, E, val;
	node(int _s, int _e) : S(_s), E(_e), val(1e17) {
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	int qry(int l, int r) {
		if (l > E || r < S) return 1e17;
		if (l <= S && E <= r) return val;
		return min(left->qry(l, r), right->qry(l, r));
	}
	void upd(int p, int v) {
		if (S == E) {
			val = v;
			return;
		}
		int M = (S + E) >> 1;
		if (p <= M) left->upd(p, v);
		else right->upd(p, v);
		val = min(left->val, right->val);
	}
} *root;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	root = new node(1, M);
	for (int i = 1; i <= M; i++) {
		cin >> T[i] >> L[i] >> R[i] >> C[i];
		K[i] = mt(R[i], L[i], T[i], C[i]);
	}
	sort(K + 1, K + 1 + M);
	for (int i = 1; i <= M; i++)
		tie(R[i], L[i], T[i], C[i]) = K[i];
	if (R[M] != N) return cout << "-1\n", 0;
	for (int i = 1; i <= M; i++) {
		int lo = 1, hi = i - 1, ans = -1;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			if (L[i] - 1 <= R[mid]) ans = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		dp[i] = 1e17;
		if (ans != -1) dp[i] = root->qry(ans, i - 1) + C[i];
		if (L[i] == 1) dp[i] = C[i];
		root->upd(i, dp[i]);
		if (R[i] == N) out = min(out, dp[i]);
	}
	cout << (out == 1e17 ? -1 : out) << '\n';
}

Compilation message (stderr)

treatment.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main() {
      | ^~~~

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