Submission #217605

#	Time	Username	Problem	Language	Result	Execution time	Memory
217605		Toadologist	Treatment Project (JOI20_treatment)	C++11	5 / 100	215 ms	205428 KiB

treatment

#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
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61