oj.uz

Submission #960020

# Submission time Handle Problem Language Result Execution time Memory
960020 2024-04-09T13:51:25 Z LCJLY Pinball (JOI14_pinball) C++14
51 / 100
 862 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
//typedef pair<pii,pii>pi2;
typedef array<int,3>pi2;

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

inline int combine(int a, int b){
	return min(a,b);
}

struct node{
	int s,e,m;
	node *l,*r;
	int v;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL),v(1e15){
	}
	
	inline void inst(){
		if(l==NULL) l=new node(s,m);
		if(r==NULL) r=new node(m+1,e);
	}
	
	void upd(int x, int y){
		if(s==e){
			v=min(v,y);
			return;
		}
		inst();
		if(x<=m) l->upd(x,y);
		else r->upd(x,y);
		v=combine(l->v,r->v);
	}
	
	int query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		inst();
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};

void solve(){
	int n,m;
	cin >> n >> m;
	array<int,4>arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x][0] >> arr[x][1] >> arr[x][2] >> arr[x][3];
	}
	
	node st(0,m+5);
	int prefix[n+5];
	st.upd(1,0);
	for(int x=0;x<n;x++){
		prefix[x]=1e15;
		
		int hold=st.query(arr[x][0],arr[x][1])+arr[x][3];
		st.upd(arr[x][2],hold);
		prefix[x]=hold;
	}
	
	node st2(0,m+5);
	int suffix[n+5];
	st2.upd(m,0);
	for(int x=0;x<n;x++){
		suffix[x]=1e15;
		
		int hold=st2.query(arr[x][0],arr[x][1])+arr[x][3];
		st2.upd(arr[x][2],hold);
		suffix[x]=hold;
	}
	
	int best=1e16;
	for(int x=0;x<n;x++){
		//show2(prefix[x],prefix[x],suffix[x],suffix[x]);
		best=min(best,prefix[x]+suffix[x]-arr[x][3]);
	}
	
	if(best>=1e15) cout << -1;
	else cout << best;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 2 ms 1140 KB Output is correct
12 Correct 4 ms 2908 KB Output is correct
13 Correct 2 ms 3160 KB Output is correct
14 Correct 3 ms 3164 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 2 ms 1140 KB Output is correct
12 Correct 4 ms 2908 KB Output is correct
13 Correct 2 ms 3160 KB Output is correct
14 Correct 3 ms 3164 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 3 ms 1884 KB Output is correct
17 Correct 5 ms 5212 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 9 ms 11528 KB Output is correct
20 Correct 4 ms 3676 KB Output is correct
21 Correct 3 ms 3420 KB Output is correct
22 Correct 11 ms 11352 KB Output is correct
23 Correct 10 ms 13148 KB Output is correct
24 Correct 11 ms 13392 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 2 ms 1140 KB Output is correct
12 Correct 4 ms 2908 KB Output is correct
13 Correct 2 ms 3160 KB Output is correct
14 Correct 3 ms 3164 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 3 ms 1884 KB Output is correct
17 Correct 5 ms 5212 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 9 ms 11528 KB Output is correct
20 Correct 4 ms 3676 KB Output is correct
21 Correct 3 ms 3420 KB Output is correct
22 Correct 11 ms 11352 KB Output is correct
23 Correct 10 ms 13148 KB Output is correct
24 Correct 11 ms 13392 KB Output is correct
25 Correct 29 ms 20684 KB Output is correct
26 Correct 147 ms 110660 KB Output is correct
27 Correct 413 ms 190752 KB Output is correct
28 Correct 171 ms 12308 KB Output is correct
29 Correct 375 ms 226388 KB Output is correct
30 Correct 416 ms 47804 KB Output is correct
31 Correct 862 ms 409560 KB Output is correct
32 Correct 835 ms 278356 KB Output is correct
33 Correct 95 ms 94808 KB Output is correct
34 Correct 453 ms 397076 KB Output is correct
35 Runtime error 591 ms 524288 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -