Submission #571336

#	Time	Username	Problem	Language	Result	Execution time	Memory
571336		sidon	Treatment Project (JOI20_treatment)	C++17	4 / 100	740 ms	129536 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 {};

	for(auto &[R, L, T, C] : a) {
		cin >> T >> L >> R >> C;
		c[p++] = T;
	}

	sort(a, a + M);
	sort(c, c + M);
	
	set<array<int, 2>> s[2][M + 1];
	int ans = INF;

	for(auto [R, L, T, C] : a) {
		int cur = L < 2 ? 0 : INF, t = lower_bound(c, c + M, T) - c;

		for(int i = 0; i < 2; ++i) {
			int f = L + (i ? T : -T) - 1;

			for(int k = (i ? t + 1 : M - t); k > 0; k -= k&-k) {
				if(!empty(s[i][k]) && f <= (*--end(s[i][k]))[0])
					cur = min(cur, (*s[i][k].lower_bound({f}))[1]);
			}
		}
		cur = min(cur + C, INF);

		if(R == N) ans = min(ans, cur);

		for(int i = 0; i < 2; ++i) {
			int f = R + (i ? T : -T);

			for(int k = (i ? t + 1 : M - t); k <= M; k += k&-k) {

				auto j = s[i][k].insert({f, cur}).first;

				if(next(j) != end(s[i][k]) && (*next(j))[1] <= cur)
					s[i][k].erase(j);
				else {
					while(j != begin(s[i][k]) && (*prev(j))[1] >= cur)
						s[i][k].erase(prev(j));
				}
			}
		}
	}

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

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