oj.uz

답안 #111415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
111415 2019-05-15T10:32:12 Z vex Pinball (JOI14_pinball) C++14
11 / 100
 3 ms 384 KB 
/**11:37**/
#include<bits/stdc++.h>
#define maxn 100010
#define INF 100000000000000000
using namespace std;

int m,n;
int a[maxn],b[maxn],c[maxn],d[maxn];
map<int,bool> bio;

int len;
vector<int>poz;
long long dis[4*maxn][2];

void build(int v,int l,int r,int type)
{
	if(l==r)
	{
		if((type==0 && l==0) || (type==1 && l==len-1))dis[v][type]=0;
		else dis[v][type]=INF;
		return;
	}
	
	int mid=(l+r)/2;
	build(2*v,l,mid,type);
	build(2*v+1,mid+1,r,type);
	
	dis[v][type]=min(dis[2*v][type],dis[2*v+1][type]);
}

long long minn(int v,int l,int r,int lt,int rt,int type)
{
	if(l>r || rt<l || lt>r)return INF;
	
	if(lt<=l && r<=rt)return dis[v][type];
	
	int mid=(l+r)/2;
	return min(minn(2*v,l,mid,lt,rt,type),minn(2*v+1,mid+1,r,lt,rt,type));
}

void update(int v,int l,int r,int ind,long long vre,int type)
{
	if(l>r || l>ind || ind>r)return;
	
	if(l==r)
	{
		dis[v][type]=vre;
		return;
	}	
		
	int mid=(l+r)/2;
	update(2*v,l,mid,ind,vre,type);
	update(2*v+1,mid+1,r,ind,vre,type);
	dis[v][type]=min(dis[2*v][type],dis[2*v+1][type]);
}

long long ras[maxn][2];
void prodji(int v,int l,int r,int type)
{
	if(l>r)return;
	
	if(l==r)
	{
		ras[l][type]=dis[v][type];
		return;
	}
	
	int mid=(l+r)/2;
	prodji(2*v,l,mid,type);
	prodji(2*v+1,mid+1,r,type);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin>>m>>n;
	bio[1]=bio[n]=true;
	poz.push_back(1);
	poz.push_back(n);
	for(int i=1;i<=m;i++)
	{
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		if(!bio[c[i]])poz.push_back(c[i]);
		bio[c[i]]=true;
	}
	
	sort(poz.begin(),poz.end());
	len=poz.size();
	//for(int i=0;i<len;i++)cout<<poz[i]<<" ";cout<<endl;
	
	for(int i=1;i<=m;i++)
	{
		a[i]=lower_bound(poz.begin(),poz.end(),a[i])-poz.begin();
		b[i]=upper_bound(poz.begin(),poz.end(),b[i])-poz.begin()-1;
		//cout<<i<<": "<<a[i]<<","<<b[i]<<endl;
	}
	
	long long res=INF;
	for(int type=0;type<2;type++){build(1,0,len-1,type);}
	for(int i=1;i<=m;i++)
	{
		long long cena=minn(1,0,len-1,a[i],b[i],0);
		int pos=lower_bound(poz.begin(),poz.end(),c[i])-poz.begin();
		long long tre=minn(1,0,len-1,pos,pos,0);
		if(cena+d[i]<tre)update(1,0,len-1,pos,cena+d[i],0);
		
		
		long long cena1=minn(1,0,len-1,a[i],b[i],1);
		if(cena1+min(cena+d[i],tre)<res)res=cena1+min(cena+d[i],tre);
		
		long long tre1=minn(1,0,len-1,pos,pos,1);
		if(cena1+d[i]<tre1)update(1,0,len-1,pos,cena1+d[i],1);
	}
	
	if(res==INF)cout<<"-1"<<endl;
	else cout<<res<<endl;
	return 0;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 49.0

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