Submission #423956

#	Time	Username	Problem	Language	Result	Execution time	Memory
423956		oolimry	Treatment Project (JOI20_treatment)	C++17	4 / 100	500 ms	428048 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<int,int> ii;

struct thing{
	lint t, l, r, c;
};
vector<thing> arr;

struct node{
	lint s, e, m;
	lint val = 10234567890123456;
	node *l = nullptr, *r = nullptr;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
	}
	
	inline void create(){
		if(s != e and l == nullptr){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	lint query(int S, int E){
		create();
		if(s == S and e == E) return val;
		else if(E <= m) return l->query(S, E);
		else if(S >= m+1) return r->query(S, E);
		else return min(l->query(S, m), r->query(m+1, E));
	}
	
	void update(int P, lint X){
		create();
		if(s == e) val = min(X, val);
		else{
			if(P <= m) l->update(P, X);
			else r->update(P, X);
			val = min(l->val, r->val);
		}
	}
	
} *root = new node(0, 1000000005);

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int L, n; cin >> L >> n;
	for(int i = 0;i < n;i++){
		int t, l, r, c; cin >> t >> l >> r >> c;
		arr.push_back({t,l,r,c});
	}
	
	root->update(0,0);
	
	sort(all(arr), [&](thing a, thing b){ return a.r < b.r; });
	
	for(thing &t : arr){
		lint dp = root->query(t.l-1, t.r) + t.c;
		root->update(t.r, dp);
	}
	
	lint ans = root->query(L,L);
	if(ans > 10232567890123456LL) ans = -1;
	cout << ans;
}

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