oj.uz

Submission #423815

# Submission time Handle Problem Language Result Execution time Memory
423815 2021-06-11T13:00:36 Z pavement Treatment Project (JOI20_treatment) C++17
4 / 100
 131 ms 16744 KB 
#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

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 16728 KB Output is correct
2 Correct 94 ms 16732 KB Output is correct
3 Correct 108 ms 16692 KB Output is correct
4 Correct 98 ms 16636 KB Output is correct
5 Correct 97 ms 16716 KB Output is correct
6 Correct 98 ms 16740 KB Output is correct
7 Correct 95 ms 16616 KB Output is correct
8 Correct 102 ms 16708 KB Output is correct
9 Correct 97 ms 16624 KB Output is correct
10 Correct 91 ms 16708 KB Output is correct
11 Correct 115 ms 16744 KB Output is correct
12 Correct 121 ms 16728 KB Output is correct
13 Correct 112 ms 16728 KB Output is correct
14 Correct 131 ms 16736 KB Output is correct
15 Correct 112 ms 16616 KB Output is correct
16 Correct 101 ms 16708 KB Output is correct
17 Correct 97 ms 16632 KB Output is correct
18 Correct 110 ms 16624 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 3 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 3 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 16728 KB Output is correct
2 Correct 94 ms 16732 KB Output is correct
3 Correct 108 ms 16692 KB Output is correct
4 Correct 98 ms 16636 KB Output is correct
5 Correct 97 ms 16716 KB Output is correct
6 Correct 98 ms 16740 KB Output is correct
7 Correct 95 ms 16616 KB Output is correct
8 Correct 102 ms 16708 KB Output is correct
9 Correct 97 ms 16624 KB Output is correct
10 Correct 91 ms 16708 KB Output is correct
11 Correct 115 ms 16744 KB Output is correct
12 Correct 121 ms 16728 KB Output is correct
13 Correct 112 ms 16728 KB Output is correct
14 Correct 131 ms 16736 KB Output is correct
15 Correct 112 ms 16616 KB Output is correct
16 Correct 101 ms 16708 KB Output is correct
17 Correct 97 ms 16632 KB Output is correct
18 Correct 110 ms 16624 KB Output is correct
19 Correct 0 ms 332 KB Output is correct
20 Incorrect 3 ms 332 KB Output isn't correct
21 Halted 0 ms 0 KB -