Submission #897325

#	Time	Username	Problem	Language	Result	Execution time	Memory
897325		guechotjrhh	Treatment Project (JOI20_treatment)	C++14	100 / 100	1633 ms	138300 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
#define maxn (1<<17)
#define maxs (1<<18)
ll min(ll a, ll b) { return a < b ? a : b; }
ll ab(ll n) { return n > 0 ? n : -n; }

vector<int> le(maxs), ri(maxs);
vector<set<pi>> v(maxs);
void bld() {
	for (int i = maxn; i < maxs; i++) {
		le[i] = ri[i] = i - maxn;
	}
	for (int i = maxn - 1; i > 0; i--) {
		le[i] = le[i << 1];
		ri[i] = ri[(i << 1) + 1];
	}
}
void insert(int i, int j, int ind) {
	//cout << i << ' ' << j << ' ' << ind << endl;
	i = 2 * (i + maxn);
	while (i >>= 1) v[i].insert({j, ind});
}
void del(int i, int j, int ind) {
	i = 2 * (i + maxn);
	while (i >>= 1) v[i].erase(v[i].find({ j, ind }));
}
void que(int i, int ex, int ey,vi&res) {
	if (le[i] > ex) return;
	if (ri[i] <= ex) {
		//for (auto it : v[i]) {cout << it.x << ' ' << it.y << "   ";}cout << endl;

		for (auto it : v[i]) {
			if (it.x > ey) break;
			res.push_back(it.y);
		}
	}
	else {
		que(i << 1, ex, ey, res);
		que((i << 1)+1, ex, ey, res);
	}
}

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;
	bld();

	//N <= 5000
	//vector<pair<pi, pi>> vec(n);
	//for (int i = 0; i < n; i++)	vec[i] = { {L[i],R[i]}, {T[i],P[i]} };
	map<int, int> mp;
	for (int i = 0; i < n; i++) mp[L[i] - T[i]] = 0;
	int c = 0;
	for (auto it : mp) mp[it.x] = c++;

	//vector<ll> dist(n, 1e18);
	//for (int i = 0; i < n; i++) if (L[i] == 1) dist[i] = P[i];
	ll res = 1e18;
	set<pair<ll, int>> st;
	for (int i = 0; i < n; i++) {
		if (L[i] == 1) st.insert({ P[i],i });
		else insert(mp[L[i]-T[i]],L[i]+T[i],i);

	}
	while (st.size()) {
		auto it = st.begin();
		int i = it->y;
		ll dst = it->x;
		st.erase(it);
		//cout << i << ' ' << dst << endl;
		if (R[i] == s) res = min(res, dst);

		auto lt = mp.upper_bound(R[i] - T[i] + 1);
		if (lt == mp.begin()) continue;
		lt--;
		int u = lt->y;
		//cout << u << endl;
		vector<int> vec;
		que(1, u, R[i]+T[i]+1, vec);
		//cout << "vec: "; for (int j : vec) cout << j << ' '; cout << endl;
		for (int j : vec) {
			st.insert({ dst + P[j],j });
			del(mp[L[j] - T[j]], L[j] + T[j], j);
		}
		/*for (int j = 0; j < n; j++) {
			if (R[i] - T[i] + 1 >= L[j] - T[j] && R[i] + T[i] + 1 >= L[j] + T[j]) {
				if (dist[j] > P[j] + dst) {
					st.erase(st.find({ dist[j],j }));
					dist[j] = P[j] + dst;
					st.insert({ dist[j],j });
				}
			}
		}*/
	}
	//ll res = 1e18;
	//for (int i = 0; i < n; i++) if (R[i] == s && dist[i] < res) res = dist[i];
	return res == 1e18 ? -1 : res;

	/*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 = "03-00.txt";
	for (int i = 1; i <= 18; i++) {
		cout << "TEST " << i << endl;
		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: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61