Submission #897579

#	Time	Username	Problem	Language	Result	Execution time	Memory
897579		guechotjrhh	Treatment Project (JOI20_treatment)	C++14	100 / 100	360 ms	60364 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), ind(maxs,0);
//vector<set<pi>> v(maxs);
vector<vector<pi>> v(maxs);
void bld() {
	for (int i = maxn; i < maxs; i++) {
		le[i] = ri[i] = i - maxn;
		v[i].clear();
		ind[i] = 0;
	}
	for (int i = maxn - 1; i > 0; i--) {
		le[i] = le[i << 1];
		ri[i] = ri[(i << 1) + 1];
		v[i].clear();
		ind[i] = 0;
	}
}
void insert(int i, int j, int ind) {
	i = 2 * (i + maxn);
	while (i >>= 1) v[i].push_back({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 (; ind[i] < v[i].size() && v[i][ind[i]].x <= ey; ind[i]++) res.push_back(v[i][ind[i]].y);
		/*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();
	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++;
	ll res = 1e18;
	set<pair<ll, int>> st;
	vector < pi>vc(n);
	for (int i = 0; i < n; i++) vc[i] = {L[i]+T[i], i};
	sort(all(vc));
	for (int i = 0; i < n; i++) if (L[vc[i].y] != 1) insert(mp[L[vc[i].y]-T[vc[i].y]], vc[i].x, vc[i].y);
	vector<bool> ve(n, 0);
	for (int i = 0; i < n; i++) {
		if (L[i] == 1) {
			st.insert({ P[i],i });
			ve[i] = 1;
		}
		//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);
		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;
		vector<int> vec;
		que(1, u, R[i]+T[i]+1, vec);
		for (int j : vec) {
			if (!ve[j]) {
				ve[j] = 1;
				st.insert({ dst + P[j],j });
			}
			//del(mp[L[j] - T[j]], L[j] + T[j], j);
		}
	}
	return res == 1e18 ? -1 : res;
}

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;
}

Compilation message (stderr)

treatment.cpp: In function 'void que(int, int, int, std::vector<int>&)':
treatment.cpp:50:17: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for (; ind[i] < v[i].size() && v[i][ind[i]].x <= ey; ind[i]++) res.push_back(v[i][ind[i]].y);

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