Submission #1219649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219649		siewjh	Treatment Project (JOI20_treatment)	C++20	100 / 100	257 ms	30672 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
vector<int> dsct;
vector<pair<int, int>> inct[MAXN], dect[MAXN];
int pro[MAXN];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, M; cin >> N >> M; N++;
	vector<tuple<int, int, int, ll>> pa(M);
	for (int i = 0; i < M; i++){
		int t, l, r; ll c; cin >> t >> l >> r >> c; r++;
		pa[i] = {t, l, r, c};
		dsct.push_back(t);
	}
	sort(dsct.begin(), dsct.end());
	dsct.resize(distance(dsct.begin(), unique(dsct.begin(), dsct.end())));
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	for (int i = 0; i < M; i++){
		int t, l, r; ll c; tie(t, l, r, c) = pa[i];
		int tid = lower_bound(dsct.begin(), dsct.end(), t) - dsct.begin() + 1;
		for (int x = M - tid + 1; x <= M; x += (x & -x)) inct[x].push_back({l + t, i});
		for (int x = tid; x <= M; x += (x & -x)) dect[x].push_back({l - t, i});
		if (l == 1){
			pro[i] = 1; pq.push({c, i});
		}
	}
	for (int i = 1; i <= M; i++){
		sort(inct[i].begin(), inct[i].end(), greater<pair<ll, int>>());
		sort(dect[i].begin(), dect[i].end(), greater<pair<ll, int>>());
	}
	while (!pq.empty()){
		ll cc; int cn; tie(cc, cn) = pq.top(); pq.pop();
		int t, l, r; tie(t, l, r, ignore) = pa[cn];
		if (r == N){
			cout << cc; return 0;
		}
		int tid = lower_bound(dsct.begin(), dsct.end(), t) - dsct.begin() + 1;
		for (int x = M - tid + 1; x; x -= (x & -x))
			while (!inct[x].empty() && inct[x].back().first <= r + t){
				int nn = inct[x].back().second; inct[x].pop_back();
				if (pro[nn]) continue;
				pro[nn] = 1; pq.push({cc + get<3>(pa[nn]), nn});
			}
		for (int x = tid; x; x -= (x & -x))
			while (!dect[x].empty() && dect[x].back().first <= r - t){
				int nn = dect[x].back().second; dect[x].pop_back();
				if (pro[nn]) continue;
				pro[nn] = 1; pq.push({cc + get<3>(pa[nn]), nn});
			}
	}
	cout << -1;
}

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