Submission #571344

#	Time	Username	Problem	Language	Result	Execution time	Memory
571344		sidon	Treatment Project (JOI20_treatment)	C++17	100 / 100	551 ms	56096 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
#define int long long

int INF = 1e18;

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int N, M; cin >> N >> M;

	array<int, 4> a[M];
	int c[M], p {};
	bool vis[M] {};
	priority_queue<array<int, 2>> q, s[2][M + 1];

	for(auto &[T, L, R, C] : a) {
		cin >> T >> L >> R >> C;
		if(R == N) q.push({-C, p}), vis[p] = 1;
		c[p++] = T;
	}

	sort(c, c + M);

	for(int i = 0; i < M; ++i) if(!vis[i]) {
		auto [T, L, R, C] = a[i];
		for(int j = 0; j < 2; ++j) {
			int f = R + (j ? T : -T), t = lower_bound(c, c + M, T) - c;

			for(int k = (j ? t + 1 : M - t); k <= M; k += k&-k)
				s[j][k].push({f, i});
		}
	}
	
	int ans = INF;

	while(!empty(q)) {
		auto [d, u] = q.top(); q.pop();
		d = -d;
		auto [T, L, R, C] = a[u];
		int t = lower_bound(c, c + M, T) - c;

		for(int j = 0; j < 2; ++j) {
			int f = L + (j ? T : -T) - 1;
			for(int k = (j ? t + 1 : M - t); k > 0; k -= k&-k) {
				while(1) {
					while(!empty(s[j][k]) && vis[s[j][k].top()[1]])
						s[j][k].pop();

					if(!empty(s[j][k]) && f <= s[j][k].top()[0]) {
						int v = s[j][k].top()[1]; s[j][k].pop();
						vis[v] = 1;
						q.push({-(d + a[v][3]), v});
					} else break;
				}
			}
		}
		if(L < 2) ans = min(ans, d);
	}

	cout << (ans == INF ? -1 : ans);
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61