oj.uz

답안 #975568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975568 2024-05-05T13:31:44 Z PM1 Pinball (JOI14_pinball) C++17
0 / 100
 1 ms 6608 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=1e5+5,sz=(1<<19);
ll n,m,g[mxn][4];
vector<int>v;
struct segment{
	ll mn[sz];
	void up(int id,int L,int R,int l,ll x,bool w){
		if(L+1==R){
			if(w==1 || mn[id]>x){
				mn[id]=x;
			}
			return;
		}
		int mid=(L+R)/2;
		if(l<mid)
			up(id*2,L,mid,l,x,w);
		else
			up(id*2+1,mid,R,l,x,w);
		if(mn[id*2]<mn[id*2+1])
			mn[id]=mn[id*2];
		else
			mn[id]=mn[id*2+1];
	}
	ll get(int id,int L,int R,int l,int r){
		if(L==l && R==r){
			return mn[id];
		}
		ll x1=1e16,x2=1e16;
		int mid=(L+R)/2;
		if(l<mid)
			x1=get(id*2,L,mid,l,min(r,mid));
		if(r>mid)
			x2=get(id*2+1,mid,R,max(l,mid),r);
		return min(x1,x2);
	}
}seg[3];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=0;j<3;j++){
			cin>>g[i][j];
			v.push_back(g[i][j]);
		}
		cin>>g[i][3];
	}
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());
	for(int i=1;i<=m;i++){
		for(int j=0;j<3;j++){
			int x=lower_bound(v.begin(),v.end(),g[i][j])-v.begin();
			g[i][j]=x;
		}
	}
	if(v.back()!=n){
		cout<<-1;
		return 0;
	}
	n=v.size()-1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<3;j++){
			seg[j].up(1,0,n+1,i,1e16,1);
		}
	}
	seg[0].up(1,0,n+1,0,0,1);
	seg[1].up(1,0,n+1,n,0,1);
	for(int i=1;i<=m;i++){
		ll x=seg[0].get(1,0,n+1,g[i][0],g[i][1]+1);
		ll y=seg[1].get(1,0,n+1,g[i][0],g[i][1]+1);
		//cout<<x<<" "<<y<<'\n';
		seg[2].up(1,0,n+1,g[i][2],x+y+g[i][3],0);
		seg[0].up(1,0,n+1,g[i][2],x+g[i][3],0);
		seg[1].up(1,0,n+1,g[i][2],y+g[i][3],0);
	}
	ll ans=seg[2].get(1,0,n+1,0,n+1);
	if(ans==1e16)
		ans=-1;
	cout<<ans;
	return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6608 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Incorrect 1 ms 6488 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6608 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Incorrect 1 ms 6488 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6608 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Incorrect 1 ms 6488 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6608 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Incorrect 1 ms 6488 KB Output isn't correct
8 Halted 0 ms 0 KB -