oj.uz

Submission #423956

# Submission time Handle Problem Language Result Execution time Memory
423956 2021-06-11T14:41:58 Z oolimry Treatment Project (JOI20_treatment) C++17
4 / 100
 500 ms 428048 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 321456 KB Output is correct
2 Correct 387 ms 321532 KB Output is correct
3 Correct 97 ms 9652 KB Output is correct
4 Correct 102 ms 9628 KB Output is correct
5 Correct 93 ms 4544 KB Output is correct
6 Correct 118 ms 8296 KB Output is correct
7 Correct 150 ms 43548 KB Output is correct
8 Correct 95 ms 4484 KB Output is correct
9 Correct 99 ms 8340 KB Output is correct
10 Correct 134 ms 44092 KB Output is correct
11 Correct 467 ms 331416 KB Output is correct
12 Correct 477 ms 330524 KB Output is correct
13 Correct 493 ms 427440 KB Output is correct
14 Correct 497 ms 427172 KB Output is correct
15 Correct 489 ms 427964 KB Output is correct
16 Correct 500 ms 427684 KB Output is correct
17 Correct 484 ms 428048 KB Output is correct
18 Correct 470 ms 330932 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 321456 KB Output is correct
2 Correct 387 ms 321532 KB Output is correct
3 Correct 97 ms 9652 KB Output is correct
4 Correct 102 ms 9628 KB Output is correct
5 Correct 93 ms 4544 KB Output is correct
6 Correct 118 ms 8296 KB Output is correct
7 Correct 150 ms 43548 KB Output is correct
8 Correct 95 ms 4484 KB Output is correct
9 Correct 99 ms 8340 KB Output is correct
10 Correct 134 ms 44092 KB Output is correct
11 Correct 467 ms 331416 KB Output is correct
12 Correct 477 ms 330524 KB Output is correct
13 Correct 493 ms 427440 KB Output is correct
14 Correct 497 ms 427172 KB Output is correct
15 Correct 489 ms 427964 KB Output is correct
16 Correct 500 ms 427684 KB Output is correct
17 Correct 484 ms 428048 KB Output is correct
18 Correct 470 ms 330932 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Incorrect 1 ms 308 KB Output isn't correct
21 Halted 0 ms 0 KB -