Submission #265332

#	Time	Username	Problem	Language	Result	Execution time	Memory
265332		dennisstar	Treatment Project (JOI20_treatment)	C++17	100 / 100	340 ms	29672 KiB

treatment

#include <bits/stdc++.h>
#define fi first
#define se second
#define em emplace
#define eb emplace_back
using namespace std;
using ll = long long;
using pli = pair<ll, int>;

const int INF = 1e9;
const int MX = 1e5 + 5;

int N, M;
int T[MX], L[MX], R[MX], C[MX], U[MX];
vector<int> cp;

priority_queue<pli> st[MX];
vector<int> v;

void upd(int t, int x) {
	while (t<=cp.size())
		st[t].em(-(L[x]+T[x]), x), t+=t&-t;
}

void get(int t, int x) {
	while (t) {
		while (st[t].size()&&-st[t].top().fi<=x)
			v.eb(st[t].top().se),
			st[t].pop();
		t-=t&-t;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin>>N>>M;
	for (int i=1; i<=M; i++)
		cin>>T[i]>>L[i]>>R[i]>>C[i],
		cp.eb(L[i]-T[i]);
	
	sort(cp.begin(), cp.end());
	cp.resize(unique(cp.begin(), cp.end())-cp.begin());

	for (int i=1; i<=M; i++)
		upd(lower_bound(cp.begin(), cp.end(), L[i]-T[i])-cp.begin()+1, i);

	priority_queue<pli> pq;
	for (int i=1; i<=M; i++) if (L[i]==1)
		pq.em(-C[i], i),
		U[i]=1;

	while (pq.size()) {
		auto k=pq.top();
		pq.pop();

		int n=k.se;
		if (R[n]==N) {
			cout<<-k.fi<<'\n';
			return 0;
		}

		v.clear();
		get(upper_bound(cp.begin(), cp.end(), R[n]-T[n]+1)-cp.begin(), R[n]+T[n]+1);

		for (auto &i:v) if (!U[i]) {
			U[i]=1;
			pq.em(k.fi-C[i], i);
		}
	}

	cout<<"-1\n";
	return 0;
}

Compilation message (stderr)

treatment.cpp: In function 'void upd(int, int)':
treatment.cpp:21:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  while (t<=cp.size())
      |         ~^~~~~~~~~~~

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