oj.uz

Submission #217612

# Submission time Handle Problem Language Result Execution time Memory
217612 2020-03-30T11:01:38 Z Toadologist Treatment Project (JOI20_treatment) C++11
5 / 100
 262 ms 270372 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 262 ms 270372 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 74 ms 131832 KB Output is correct
2 Correct 73 ms 131832 KB Output is correct
3 Correct 72 ms 131832 KB Output is correct
4 Correct 73 ms 131832 KB Output is correct
5 Correct 74 ms 131832 KB Output is correct
6 Correct 73 ms 131832 KB Output is correct
7 Correct 73 ms 131960 KB Output is correct
8 Correct 75 ms 131832 KB Output is correct
9 Correct 78 ms 131832 KB Output is correct
10 Correct 73 ms 131832 KB Output is correct
11 Correct 73 ms 131832 KB Output is correct
12 Correct 72 ms 131960 KB Output is correct
13 Correct 73 ms 131832 KB Output is correct
14 Correct 74 ms 131960 KB Output is correct
15 Correct 77 ms 131960 KB Output is correct
16 Correct 73 ms 131832 KB Output is correct
17 Correct 75 ms 131832 KB Output is correct
18 Correct 73 ms 131960 KB Output is correct
19 Correct 75 ms 131960 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 131832 KB Output is correct
2 Correct 73 ms 131832 KB Output is correct
3 Correct 72 ms 131832 KB Output is correct
4 Correct 73 ms 131832 KB Output is correct
5 Correct 74 ms 131832 KB Output is correct
6 Correct 73 ms 131832 KB Output is correct
7 Correct 73 ms 131960 KB Output is correct
8 Correct 75 ms 131832 KB Output is correct
9 Correct 78 ms 131832 KB Output is correct
10 Correct 73 ms 131832 KB Output is correct
11 Correct 73 ms 131832 KB Output is correct
12 Correct 72 ms 131960 KB Output is correct
13 Correct 73 ms 131832 KB Output is correct
14 Correct 74 ms 131960 KB Output is correct
15 Correct 77 ms 131960 KB Output is correct
16 Correct 73 ms 131832 KB Output is correct
17 Correct 75 ms 131832 KB Output is correct
18 Correct 73 ms 131960 KB Output is correct
19 Correct 75 ms 131960 KB Output is correct
20 Correct 115 ms 138744 KB Output is correct
21 Correct 109 ms 138616 KB Output is correct
22 Runtime error 208 ms 267256 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 262 ms 270372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -