Submission #537366

#	Time	Username	Problem	Language	Result	Execution time	Memory
537366		8e7	Treatment Project (JOI20_treatment)	C++17	4 / 100	216 ms	33728 KiB

treatment

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
pii a[maxn];
ll cost[maxn], ans[4*maxn];
vector<pii> ev[4 * maxn];
vector<ll> del[4*maxn];
int main() {
	io
	int L, n;
	cin >> L >> n;
	vector<int> vx;
	for (int i = 1;i <= n;i++) {
		int t, l, r, c;
		cin >> t >> l >> r >> c;
		a[i] = {l, r};
		cost[i] = c;
		vx.push_back(l), vx.push_back(r), vx.push_back(l-1), vx.push_back(r+1);
	}
	sort(vx.begin(), vx.end());
	vx.resize(int(unique(vx.begin(), vx.end()) - vx.begin()));
	for (int i = 1;i <= n;i++) {
		a[i].ff = lower_bound(vx.begin(), vx.end(), a[i].ff) - vx.begin();
		a[i].ss = lower_bound(vx.begin(), vx.end(), a[i].ss) - vx.begin();
		ev[a[i].ff - 1].push_back({a[i].ss + 1, cost[i]});
	}
	if (vx[0] != 0 || vx.back() != L+1) {
		cout << -1 << endl;
		return 0;
	}
	multiset<ll> se;
	se.insert(0);
	del[1].push_back(0);	
	bool poss = 1;
	for (int i = 0;i < vx.size()-1;i++) {
		for (auto j:del[i]) {
			se.erase(se.find(j));
		}
		for (auto [t, c]:ev[i]) {
			if (se.size() == 0) {
				poss = 0;
				break;
			}
			ll val = c + *se.begin();
			del[t].push_back(val);
			se.insert(val);
		}
	}
	if (se.size() == 0) poss = 0;
	if (poss) cout << *se.begin() << "\n";
	else cout << -1 << endl;
}

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int i = 0;i < vx.size()-1;i++) {
      |                 ~~^~~~~~~~~~~~~

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