oj.uz

Submission #892582

# Submission time Handle Problem Language Result Execution time Memory
892582 2023-12-25T14:25:57 Z ReLice Pinball (JOI14_pinball) C++14
51 / 100
 257 ms 60584 KB 
#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define bc back()
#define ar array
#define vll vector<ll> 
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class _T>
bool chmin(_T &x, const _T &y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag=false;
    if (x<y){
        x=y;flag|=true;
    }
    return flag;
}
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=2e18+7;
const ll mod=1e9+7;
const ll N=1e5+7;
const ld eps=1e-9;
vll t(N*4,inf),t2(N*4,inf);
void upd(ll id,ll v,ll tl,ll tr,ll pos,ll val){
	if(tl>pos || tr<pos)return;
	if(tl==tr){
		if(id==1)chmin(t[v],val);
		else chmin(t2[v],val);
		return;
	}
	ll tm=(tl+tr)/2;
	upd(id,v*2,tl,tm,pos,val);
	upd(id,v*2+1,tm+1,tr,pos,val);
	t[v]=min(t[v*2],t[v*2+1]);
	t2[v]=min(t2[v*2],t2[v*2+1]);
}
ll get(ll id,ll v,ll tl,ll tr,ll l,ll r){
	if(tl>r || tr<l)return inf;
	if(l<=tl && tr<=r)return (id==1 ? t[v] : t2[v]);
	ll tm=(tl+tr)/2;
	return min(get(id,v*2,tl,tm,l,r),get(id,v*2+1,tm+1,tr,l,r));
}
void solve(){
	ll i,j;
	ll n,m; 
	cin>>n>>m;
	set<ll> s;
	s.ins(1);
	s.ins(m);
	vector<ar<ll,4>> v(1);
	ar<ll,4> x;
	for(i=1;i<=n;i++){
		for(j=0;j<4;j++){
			cin>>x[j];
			if(j<3)s.ins(x[j]);
		}
		v.pb(x);
	}
	map<ll,ll> pos;
	ll c=1;
	for(auto i : s){
		pos[i]=c;
		c++;
	}
	m=s.sz;
	for(i=1;i<=n;i++){
		for(j=0;j<3;j++){
			v[i][j]=pos[v[i][j]];
		}
	}
	upd(1,1,1,s.sz,1,0);
	upd(2,1,1,s.sz,s.sz,0);
	ll ans=inf;
	for(i=1;i<=n;i++){
		ll x=get(1,1,1,s.sz,v[i][0],v[i][1]),y=get(2,1,1,s.sz,v[i][0],v[i][1]);
		upd(1,1,1,s.sz,v[i][2],x+v[i][3]);
		upd(2,1,1,s.sz,v[i][2],y+v[i][3]);
		ans=min(ans,x+y+v[i][3]);
	}
	for(i=1;i<=(ll)s.sz;i++){
		ans=min(ans,get(1,1,1,s.sz,i,i)+get(2,1,1,s.sz,i,i));
	}
	if(ans==inf)cout<<-1<<endl;
	else cout<<ans<<endl;
}
signed main(){
	start();
    ll t=1;
	//cin>>t;
    while(t--) solve();
    return 0;
}
/*
1
6
5 4 3 2 1 0





*/

Compilation message

pinball.cpp: In function 'void fre(std::string)':
pinball.cpp:42:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pinball.cpp:42:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6648 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 2 ms 6900 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6648 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 2 ms 6900 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6784 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6648 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 2 ms 6900 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6784 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 2 ms 6744 KB Output is correct
17 Correct 4 ms 6748 KB Output is correct
18 Correct 3 ms 6748 KB Output is correct
19 Correct 5 ms 7016 KB Output is correct
20 Correct 4 ms 6828 KB Output is correct
21 Correct 3 ms 6776 KB Output is correct
22 Correct 5 ms 7004 KB Output is correct
23 Correct 4 ms 7004 KB Output is correct
24 Correct 5 ms 7040 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6648 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 2 ms 6900 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6784 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 2 ms 6744 KB Output is correct
17 Correct 4 ms 6748 KB Output is correct
18 Correct 3 ms 6748 KB Output is correct
19 Correct 5 ms 7016 KB Output is correct
20 Correct 4 ms 6828 KB Output is correct
21 Correct 3 ms 6776 KB Output is correct
22 Correct 5 ms 7004 KB Output is correct
23 Correct 4 ms 7004 KB Output is correct
24 Correct 5 ms 7040 KB Output is correct
25 Correct 28 ms 9172 KB Output is correct
26 Correct 87 ms 14280 KB Output is correct
27 Correct 224 ms 22776 KB Output is correct
28 Correct 129 ms 14452 KB Output is correct
29 Correct 168 ms 20124 KB Output is correct
30 Correct 215 ms 15720 KB Output is correct
31 Runtime error 257 ms 60584 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -