Submission #896449

#	Time	Username	Problem	Language	Result	Execution time	Memory
896449		guechotjrhh	Treatment Project (JOI20_treatment)	C++14	4 / 100	73 ms	14464 KiB

treatment

#include <iostream>
#include<vector>
#include<set>
#include<map>
#include<fstream>
#include<algorithm>
using namespace std;
#define ll long long
#define pi pair<ll,ll>
#define x first
#define y second
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define l x.x
#define r x.y
#define t y.x
#define p y.y

ll min(ll a, ll b) { return a < b ? a : b; }
int s, n;
long long func(int S, int N, vector<int> T, vector<int> L, vector<int> R, vector<int> P) {
	s = S; n = N;
	//t[i] == 1:
	map<int, ll> mp;
	vector<pair<pi, pi>> vec(n);
	for (int i = 0; i < n; i++) {
		vec[i] = { {L[i],R[i]}, {T[i],P[i]} };
	}
	sort(all(vec));
	mp[s + 1] = 0;
	for (int i = n - 1; i >= 0; i--) {
		auto it = mp.upper_bound(vec[i].r + 1);
		if (it != mp.begin()) {
			it--;
			if (mp.find(vec[i].l) == mp.end()) mp[vec[i].l] = vec[i].p + it->y;
			else mp[vec[i].l] = min(mp[vec[i].l], vec[i].p + it->y);

			auto it = mp.find(vec[i].l);
			while (next(it) != mp.end() && it->y < next(it)->y) mp.erase(next(it));
		}
	}
	if (mp.find(1) != mp.end()) return mp[1];
	return -1;
}

void run_tests() {
	string name = "01-00.txt";
	for (int i = 1; i <= 18; i++) {
		name[3] = '0' + i / 10;
		name[4] = '0' + i % 10;
		ifstream fin("in/" + name);
		ifstream fout("out/" + name);

		int S, N;
		fin >> S >> N;

		vector<int> T(N), L(N), R(N), P(N);
		for (int i = 0; i < N; i++) fin >> T[i] >> L[i] >> R[i] >> P[i];

		ll u = func(S, N, T, L, R, P),u1;
		fout >> u1;
		if (u != u1) {
			cout << i << endl;
			cout << S << ' ' << N << endl;
			cout << u << ' ' << u1 << endl;
			//for (int i = 0; i < N; i++) cout << T[i] << ' ' << L[i] << ' ' << R[i] << ' ' << P[i] << endl;
			return;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//run_tests();
	//return 0;

	int S, N;
	cin >> S >> N;
	
	vector<int> T(N), L(N), R(N), P(N);
	for (int i = 0; i < N; i++) cin >> T[i] >> L[i] >> R[i] >> P[i];

	cout << func(S, N, move(T), move(L), move(R), move(P)) << endl;

	return 0;
}
/*
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1

7
*/

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