oj.uz

Submission #987188

# Submission time Handle Problem Language Result Execution time Memory
987188 2024-05-22T09:11:44 Z Mohammadamin__Sh Pinball (JOI14_pinball) C++17
100 / 100
 170 ms 29968 KB 
//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimization("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 1e5 + 10, MOD = 1e9 + 7 ;
const ll INF = 1e16 + 100;

int m , n , a[maxn] , b[maxn] , c[maxn] , d[maxn];
vector<int> v;
pii tree[4*3*maxn];

void Update(int id , int L , int R , int idx , pii w){
	if(L+1 == R){
		tree[id] = {min(tree[id].F , w.F) , min(tree[id].S , w.S)};
		return;
	}
	int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
	if(idx < mid) Update(lc , L , mid , idx , w);
	else Update(rc , mid , R , idx , w);
	tree[id] = {min(tree[lc].F , tree[rc].F) , min(tree[lc].S , tree[rc].S)};
}

pii Get(int id , int L , int R , int l , int r){
	if(L == l and R == r) return tree[id];
	int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
	pii res1 = {INF,INF} , res2 = {INF,INF};
	if(l < mid) res1 = Get(lc , L , mid , l , min(r , mid));
	if(r > mid) res2 = Get(rc , mid , R , max(l , mid) , r);
	return {min(res1.F , res2.F) , min(res1.S , res2.S)};
}

int32_t main(){	
	ios_base::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	
	for(int i = 1 ; i < 12*maxn ; i++) tree[i] = {INF,INF};

	cin >> m >> n;
	for(int i = 1 ; i <= m ; i ++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		v.pb(a[i]) , v.pb(c[i]) , v.pb(b[i]); 
	}
	sort(all(v));
	if(v[0] > 1 or v.back() < n) return cout << -1 , 0;
	v.resize(unique(all(v)) - v.begin());
	n = v.size()-1;
	if(n == 0) return cout << 0 , 0;
	for(int i = 1 ; i <= m ; i++){
		a[i] = lower_bound(all(v) , a[i]) - v.begin();
		b[i] = lower_bound(all(v) , b[i]) - v.begin();
		c[i] = lower_bound(all(v) , c[i]) - v.begin();
	}
	int ans = INF;
	for(int i = 1 ; i <= m ; i++){
		pii w = Get(1 , 0 , n+1 , a[i] , b[i]+1);
		if(a[i] == 0) w.F = 0;
		if(b[i] == n) w.S = 0;
		if(w.F < INF and w.S < INF) ans = min(ans , w.F + w.S + d[i]);
		Update(1 , 0 , n+1 , c[i] , {w.F+d[i], w.S+d[i]});
	}
	cout << (ans == INF ? -1 : ans);
		
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21084 KB Output is correct
2 Correct 10 ms 21084 KB Output is correct
3 Correct 10 ms 21084 KB Output is correct
4 Correct 7 ms 21084 KB Output is correct
5 Correct 8 ms 21084 KB Output is correct
6 Correct 7 ms 21084 KB Output is correct
7 Correct 9 ms 21124 KB Output is correct
8 Correct 8 ms 21084 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21084 KB Output is correct
2 Correct 10 ms 21084 KB Output is correct
3 Correct 10 ms 21084 KB Output is correct
4 Correct 7 ms 21084 KB Output is correct
5 Correct 8 ms 21084 KB Output is correct
6 Correct 7 ms 21084 KB Output is correct
7 Correct 9 ms 21124 KB Output is correct
8 Correct 8 ms 21084 KB Output is correct
9 Correct 7 ms 21084 KB Output is correct
10 Correct 9 ms 21084 KB Output is correct
11 Correct 8 ms 21084 KB Output is correct
12 Correct 10 ms 21048 KB Output is correct
13 Correct 7 ms 21080 KB Output is correct
14 Correct 9 ms 21084 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21084 KB Output is correct
2 Correct 10 ms 21084 KB Output is correct
3 Correct 10 ms 21084 KB Output is correct
4 Correct 7 ms 21084 KB Output is correct
5 Correct 8 ms 21084 KB Output is correct
6 Correct 7 ms 21084 KB Output is correct
7 Correct 9 ms 21124 KB Output is correct
8 Correct 8 ms 21084 KB Output is correct
9 Correct 7 ms 21084 KB Output is correct
10 Correct 9 ms 21084 KB Output is correct
11 Correct 8 ms 21084 KB Output is correct
12 Correct 10 ms 21048 KB Output is correct
13 Correct 7 ms 21080 KB Output is correct
14 Correct 9 ms 21084 KB Output is correct
15 Correct 7 ms 21128 KB Output is correct
16 Correct 9 ms 21080 KB Output is correct
17 Correct 10 ms 21084 KB Output is correct
18 Correct 8 ms 21248 KB Output is correct
19 Correct 11 ms 21236 KB Output is correct
20 Correct 9 ms 21084 KB Output is correct
21 Correct 9 ms 21080 KB Output is correct
22 Correct 9 ms 21080 KB Output is correct
23 Correct 9 ms 21164 KB Output is correct
24 Correct 9 ms 21084 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21084 KB Output is correct
2 Correct 10 ms 21084 KB Output is correct
3 Correct 10 ms 21084 KB Output is correct
4 Correct 7 ms 21084 KB Output is correct
5 Correct 8 ms 21084 KB Output is correct
6 Correct 7 ms 21084 KB Output is correct
7 Correct 9 ms 21124 KB Output is correct
8 Correct 8 ms 21084 KB Output is correct
9 Correct 7 ms 21084 KB Output is correct
10 Correct 9 ms 21084 KB Output is correct
11 Correct 8 ms 21084 KB Output is correct
12 Correct 10 ms 21048 KB Output is correct
13 Correct 7 ms 21080 KB Output is correct
14 Correct 9 ms 21084 KB Output is correct
15 Correct 7 ms 21128 KB Output is correct
16 Correct 9 ms 21080 KB Output is correct
17 Correct 10 ms 21084 KB Output is correct
18 Correct 8 ms 21248 KB Output is correct
19 Correct 11 ms 21236 KB Output is correct
20 Correct 9 ms 21084 KB Output is correct
21 Correct 9 ms 21080 KB Output is correct
22 Correct 9 ms 21080 KB Output is correct
23 Correct 9 ms 21164 KB Output is correct
24 Correct 9 ms 21084 KB Output is correct
25 Correct 19 ms 21852 KB Output is correct
26 Correct 51 ms 23256 KB Output is correct
27 Correct 130 ms 26180 KB Output is correct
28 Correct 97 ms 29852 KB Output is correct
29 Correct 83 ms 25560 KB Output is correct
30 Correct 119 ms 29896 KB Output is correct
31 Correct 163 ms 29952 KB Output is correct
32 Correct 137 ms 29968 KB Output is correct
33 Correct 27 ms 22488 KB Output is correct
34 Correct 71 ms 25456 KB Output is correct
35 Correct 117 ms 29792 KB Output is correct
36 Correct 167 ms 29900 KB Output is correct
37 Correct 163 ms 29896 KB Output is correct
38 Correct 170 ms 29896 KB Output is correct