oj.uz

Submission #217605

# Submission time Handle Problem Language Result Execution time Memory
217605 2020-03-30T10:46:05 Z Toadologist Treatment Project (JOI20_treatment) C++11
5 / 100
 215 ms 205428 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;
	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;
	}
	
	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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 215 ms 205428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 99064 KB Output is correct
2 Correct 59 ms 98936 KB Output is correct
3 Correct 59 ms 98936 KB Output is correct
4 Correct 59 ms 99064 KB Output is correct
5 Correct 58 ms 99192 KB Output is correct
6 Correct 57 ms 99064 KB Output is correct
7 Correct 56 ms 98936 KB Output is correct
8 Correct 59 ms 99064 KB Output is correct
9 Correct 58 ms 98936 KB Output is correct
10 Correct 56 ms 99064 KB Output is correct
11 Correct 57 ms 99064 KB Output is correct
12 Correct 58 ms 99064 KB Output is correct
13 Correct 56 ms 98940 KB Output is correct
14 Correct 65 ms 99060 KB Output is correct
15 Correct 57 ms 99064 KB Output is correct
16 Correct 59 ms 98936 KB Output is correct
17 Correct 58 ms 99064 KB Output is correct
18 Correct 58 ms 99116 KB Output is correct
19 Correct 57 ms 98936 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 99064 KB Output is correct
2 Correct 59 ms 98936 KB Output is correct
3 Correct 59 ms 98936 KB Output is correct
4 Correct 59 ms 99064 KB Output is correct
5 Correct 58 ms 99192 KB Output is correct
6 Correct 57 ms 99064 KB Output is correct
7 Correct 56 ms 98936 KB Output is correct
8 Correct 59 ms 99064 KB Output is correct
9 Correct 58 ms 98936 KB Output is correct
10 Correct 56 ms 99064 KB Output is correct
11 Correct 57 ms 99064 KB Output is correct
12 Correct 58 ms 99064 KB Output is correct
13 Correct 56 ms 98940 KB Output is correct
14 Correct 65 ms 99060 KB Output is correct
15 Correct 57 ms 99064 KB Output is correct
16 Correct 59 ms 98936 KB Output is correct
17 Correct 58 ms 99064 KB Output is correct
18 Correct 58 ms 99116 KB Output is correct
19 Correct 57 ms 98936 KB Output is correct
20 Correct 91 ms 105848 KB Output is correct
21 Correct 91 ms 105848 KB Output is correct
22 Runtime error 178 ms 200760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 215 ms 205428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -