oj.uz

답안 #217624

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
217624 2020-03-30T11:11:04 Z Toadologist 치료 계획 (JOI20_treatment) C++11
100 / 100
 1773 ms 316008 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}

const int maxN = 100000 + 5;
int n, m;
int T[maxN], L[maxN], R[maxN];

const int NODE = 100000 * 42 + 5;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
int cnt = 0;
int root = 0;
int lson[NODE], rson[NODE];
vector<int> G[NODE];

void link(int x, int y) {
//	eprintf("link %d %d\n", x, y);
	G[x].push_back(y);
}

int insert(int o, int L, int R, int p, int u) {
	int no = ++cnt;
	if(o) link(no, o);
	lson[no] = lson[o]; rson[no] = rson[o];
	
	if(L == R) {
		link(no, u);
	} else {
		int M = L + (R - L) / 2;
		if(p <= M) lson[no] = insert(lson[o], L, M, p, u),
			link(no, lson[no]);
		else rson[no] = insert(rson[o], M + 1, R, p, u),
			link(no, rson[no]);
	}
	return no;
}
void cover(int o, int L, int R, int ql, int qr, int u) {
	if(o == 0) return;
	if(ql <= L && R <= qr) link(u, o);
	else {
		int M = L + (R - L) / 2;
		if(ql <= M) cover(lson[o], L, M, ql, qr, u);
		if(qr > M) cover(rson[o], M + 1, R, ql, qr, u);
	}
}

LL w[NODE];
LL f[NODE];


int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif
	cin >> n >> m;
	memset(w, 0, sizeof(w));
	for(int i = 1; i <= m; ++i)
		cin >> T[i] >> L[i] >> R[i] >> w[i];
	vector<int> p;
	for(int i = 1; i <= m; ++i) p.push_back(i);
	sort(p.begin(), p.end(), [&](int x, int y) {
		return T[x] < T[y];
	});
	
	vector<int> dis;
	for(int i = 1; i <= m; ++i) dis.push_back(L[i] - T[i]);
	sort(dis.begin(), dis.end());
	
	root = cnt = m + 1;
	for(int l = 0; l < m; ++l) {
		int r = l;
		while(r + 1 < m && T[p[r + 1]] == T[p[r]]) ++r;
		for(int i = l; i <= r; ++i) {
			int val = L[p[i]] - T[p[i]];
			int pos = lower_bound(dis.begin(), dis.end(), val) - dis.begin();
			root = insert(root, 0, dis.size() - 1, pos, p[i]);
		}
		for(int i = l; i <= r; ++i) {
			int val = R[p[i]] - T[p[i]] + 1;
			int pos = upper_bound(dis.begin(), dis.end(), val) - dis.begin();
			if(pos > 0) cover(root, 0, dis.size() - 1, 0, pos - 1, p[i]);
		}
		l = r;
	}
	
	reverse(p.begin(), p.end());
	dis.clear();
	for(int i = 1; i <= m; ++i) dis.push_back(L[i] + T[i]);
	sort(dis.begin(), dis.end());
	
	root = ++cnt;
	for(int l = 0; l < m; ++l) {
		int r = l;
		while(r + 1 < m && T[p[r + 1]] == T[p[r]]) ++r;
		for(int i = l; i <= r; ++i) {
			int val = L[p[i]] + T[p[i]];
			int pos = lower_bound(dis.begin(), dis.end(), val) - dis.begin();
			root = insert(root, 0, dis.size() - 1, pos, p[i]);
		}
		for(int i = l; i <= r; ++i) {
			int val = R[p[i]] + T[p[i]] + 1;
			int pos = upper_bound(dis.begin(), dis.end(), val) - dis.begin();
			if(pos > 0) cover(root, 0, dis.size() - 1, 0, pos - 1, p[i]);
		}
		l = r;
	}
	display(cnt);
	
	priority_queue< pair<LL, int> > pq;
	for(int i = 0; i <= cnt; ++i) f[i] = INF;
	for(int i = 1; i <= m; ++i) if(L[i] == 1) {
		f[i] = w[i];
		pq.emplace(-w[i], i);
	}
	while(pq.size()) {
		auto p = pq.top(); pq.pop();
		int u = p.second;
		if(f[u] != -p.first) continue;
		
//		eprintf("Dijk: (%d, %lld)\n", u, f[u]);
		for(int v : G[u]) {
			if(chmin(f[v], f[u] + w[v])) {
				pq.emplace(-f[v], v);
			}
		}
	}
	LL ans = INF;
	for(int i = 1; i <= m; ++i) if(R[i] == n)
		chmin(ans, f[i]);
	if(ans == INF) cout << -1 << endl;
	else cout << ans << endl;
	return 0;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1400 ms 312220 KB Output is correct
2 Correct 1022 ms 312044 KB Output is correct
3 Correct 1283 ms 311836 KB Output is correct
4 Correct 1322 ms 311692 KB Output is correct
5 Correct 1180 ms 308336 KB Output is correct
6 Correct 1119 ms 308084 KB Output is correct
7 Correct 1069 ms 309872 KB Output is correct
8 Correct 618 ms 306160 KB Output is correct
9 Correct 615 ms 307888 KB Output is correct
10 Correct 690 ms 309748 KB Output is correct
11 Correct 1542 ms 311256 KB Output is correct
12 Correct 1603 ms 311140 KB Output is correct
13 Correct 1703 ms 314224 KB Output is correct
14 Correct 1682 ms 314296 KB Output is correct
15 Correct 1595 ms 312164 KB Output is correct
16 Correct 1595 ms 312236 KB Output is correct
17 Correct 1545 ms 312152 KB Output is correct
18 Correct 1538 ms 311164 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 131832 KB Output is correct
2 Correct 72 ms 131832 KB Output is correct
3 Correct 73 ms 131832 KB Output is correct
4 Correct 76 ms 132088 KB Output is correct
5 Correct 74 ms 131832 KB Output is correct
6 Correct 74 ms 131832 KB Output is correct
7 Correct 73 ms 131832 KB Output is correct
8 Correct 73 ms 131832 KB Output is correct
9 Correct 76 ms 131960 KB Output is correct
10 Correct 72 ms 131832 KB Output is correct
11 Correct 72 ms 131832 KB Output is correct
12 Correct 74 ms 131832 KB Output is correct
13 Correct 72 ms 131832 KB Output is correct
14 Correct 75 ms 131832 KB Output is correct
15 Correct 71 ms 131960 KB Output is correct
16 Correct 72 ms 131832 KB Output is correct
17 Correct 71 ms 131832 KB Output is correct
18 Correct 72 ms 131832 KB Output is correct
19 Correct 73 ms 131832 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 131832 KB Output is correct
2 Correct 72 ms 131832 KB Output is correct
3 Correct 73 ms 131832 KB Output is correct
4 Correct 76 ms 132088 KB Output is correct
5 Correct 74 ms 131832 KB Output is correct
6 Correct 74 ms 131832 KB Output is correct
7 Correct 73 ms 131832 KB Output is correct
8 Correct 73 ms 131832 KB Output is correct
9 Correct 76 ms 131960 KB Output is correct
10 Correct 72 ms 131832 KB Output is correct
11 Correct 72 ms 131832 KB Output is correct
12 Correct 74 ms 131832 KB Output is correct
13 Correct 72 ms 131832 KB Output is correct
14 Correct 75 ms 131832 KB Output is correct
15 Correct 71 ms 131960 KB Output is correct
16 Correct 72 ms 131832 KB Output is correct
17 Correct 71 ms 131832 KB Output is correct
18 Correct 72 ms 131832 KB Output is correct
19 Correct 73 ms 131832 KB Output is correct
20 Correct 112 ms 138808 KB Output is correct
21 Correct 104 ms 138744 KB Output is correct
22 Correct 109 ms 138616 KB Output is correct
23 Correct 101 ms 138620 KB Output is correct
24 Correct 118 ms 138872 KB Output is correct
25 Correct 126 ms 138764 KB Output is correct
26 Correct 108 ms 138744 KB Output is correct
27 Correct 106 ms 138744 KB Output is correct
28 Correct 118 ms 138872 KB Output is correct
29 Correct 109 ms 138744 KB Output is correct
30 Correct 97 ms 138744 KB Output is correct
31 Correct 93 ms 138620 KB Output is correct
32 Correct 128 ms 139164 KB Output is correct
33 Correct 120 ms 139000 KB Output is correct
34 Correct 118 ms 138744 KB Output is correct
35 Correct 115 ms 139000 KB Output is correct
36 Correct 115 ms 138908 KB Output is correct
37 Correct 118 ms 138744 KB Output is correct

Subtask #4
61.0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1400 ms 312220 KB Output is correct
2 Correct 1022 ms 312044 KB Output is correct
3 Correct 1283 ms 311836 KB Output is correct
4 Correct 1322 ms 311692 KB Output is correct
5 Correct 1180 ms 308336 KB Output is correct
6 Correct 1119 ms 308084 KB Output is correct
7 Correct 1069 ms 309872 KB Output is correct
8 Correct 618 ms 306160 KB Output is correct
9 Correct 615 ms 307888 KB Output is correct
10 Correct 690 ms 309748 KB Output is correct
11 Correct 1542 ms 311256 KB Output is correct
12 Correct 1603 ms 311140 KB Output is correct
13 Correct 1703 ms 314224 KB Output is correct
14 Correct 1682 ms 314296 KB Output is correct
15 Correct 1595 ms 312164 KB Output is correct
16 Correct 1595 ms 312236 KB Output is correct
17 Correct 1545 ms 312152 KB Output is correct
18 Correct 1538 ms 311164 KB Output is correct
19 Correct 73 ms 131832 KB Output is correct
20 Correct 72 ms 131832 KB Output is correct
21 Correct 73 ms 131832 KB Output is correct
22 Correct 76 ms 132088 KB Output is correct
23 Correct 74 ms 131832 KB Output is correct
24 Correct 74 ms 131832 KB Output is correct
25 Correct 73 ms 131832 KB Output is correct
26 Correct 73 ms 131832 KB Output is correct
27 Correct 76 ms 131960 KB Output is correct
28 Correct 72 ms 131832 KB Output is correct
29 Correct 72 ms 131832 KB Output is correct
30 Correct 74 ms 131832 KB Output is correct
31 Correct 72 ms 131832 KB Output is correct
32 Correct 75 ms 131832 KB Output is correct
33 Correct 71 ms 131960 KB Output is correct
34 Correct 72 ms 131832 KB Output is correct
35 Correct 71 ms 131832 KB Output is correct
36 Correct 72 ms 131832 KB Output is correct
37 Correct 73 ms 131832 KB Output is correct
38 Correct 112 ms 138808 KB Output is correct
39 Correct 104 ms 138744 KB Output is correct
40 Correct 109 ms 138616 KB Output is correct
41 Correct 101 ms 138620 KB Output is correct
42 Correct 118 ms 138872 KB Output is correct
43 Correct 126 ms 138764 KB Output is correct
44 Correct 108 ms 138744 KB Output is correct
45 Correct 106 ms 138744 KB Output is correct
46 Correct 118 ms 138872 KB Output is correct
47 Correct 109 ms 138744 KB Output is correct
48 Correct 97 ms 138744 KB Output is correct
49 Correct 93 ms 138620 KB Output is correct
50 Correct 128 ms 139164 KB Output is correct
51 Correct 120 ms 139000 KB Output is correct
52 Correct 118 ms 138744 KB Output is correct
53 Correct 115 ms 139000 KB Output is correct
54 Correct 115 ms 138908 KB Output is correct
55 Correct 118 ms 138744 KB Output is correct
56 Correct 1111 ms 311152 KB Output is correct
57 Correct 1105 ms 310600 KB Output is correct
58 Correct 1030 ms 308968 KB Output is correct
59 Correct 1020 ms 308936 KB Output is correct
60 Correct 1014 ms 305972 KB Output is correct
61 Correct 1054 ms 308868 KB Output is correct
62 Correct 1111 ms 311024 KB Output is correct
63 Correct 792 ms 304072 KB Output is correct
64 Correct 794 ms 303852 KB Output is correct
65 Correct 1539 ms 311824 KB Output is correct
66 Correct 846 ms 306140 KB Output is correct
67 Correct 1511 ms 312016 KB Output is correct
68 Correct 1353 ms 311644 KB Output is correct
69 Correct 1267 ms 311600 KB Output is correct
70 Correct 1538 ms 312068 KB Output is correct
71 Correct 1359 ms 311772 KB Output is correct
72 Correct 1216 ms 311668 KB Output is correct
73 Correct 1532 ms 311912 KB Output is correct
74 Correct 698 ms 311540 KB Output is correct
75 Correct 673 ms 311156 KB Output is correct
76 Correct 1568 ms 314056 KB Output is correct
77 Correct 1532 ms 316008 KB Output is correct
78 Correct 1702 ms 313672 KB Output is correct
79 Correct 1549 ms 311832 KB Output is correct
80 Correct 1651 ms 311488 KB Output is correct
81 Correct 852 ms 311536 KB Output is correct
82 Correct 1773 ms 311636 KB Output is correct
83 Correct 1696 ms 311972 KB Output is correct
84 Correct 1553 ms 311668 KB Output is correct
85 Correct 1105 ms 311796 KB Output is correct
86 Correct 1116 ms 311764 KB Output is correct
87 Correct 1184 ms 311672 KB Output is correct
88 Correct 1190 ms 310004 KB Output is correct
89 Correct 1207 ms 311536 KB Output is correct
90 Correct 1482 ms 314096 KB Output is correct
91 Correct 1370 ms 312960 KB Output is correct
92 Correct 1190 ms 311668 KB Output is correct
93 Correct 1515 ms 311792 KB Output is correct
94 Correct 1434 ms 309876 KB Output is correct
95 Correct 1403 ms 311156 KB Output is correct
96 Correct 1572 ms 314344 KB Output is correct
97 Correct 1592 ms 314732 KB Output is correct
98 Correct 1586 ms 314988 KB Output is correct
99 Correct 1644 ms 314600 KB Output is correct
100 Correct 1283 ms 309476 KB Output is correct
101 Correct 1638 ms 314608 KB Output is correct
102 Correct 1524 ms 314224 KB Output is correct
103 Correct 1194 ms 312564 KB Output is correct