Submission #53874

#	Time	Username	Problem	Language	Result	Execution time	Memory
53874		milisav	Pinball (JOI14_pinball)	C++14	51 / 100	1057 ms	155108 KiB

pinball

#include<bits/stdc++.h>
using namespace std;
long long int inf=1e18 + 1;
struct node
{
	long long int t;
	node* l;
	node* r;
	node(long long int c) {
		t=c;
		l=nullptr;
		r=nullptr;
	}
};
void insert(long long int f,int c,int x,int y,node* &t)
{
	if(t==nullptr) t=new node(f);
	t->t=min(t->t,f);
	if(x==y) return;
	int m=(x+y)>>1;
	if(c<=m) insert(f,c,x,m,t->l);
	else insert(f,c,m+1,y,t->r);
}
long long int query(int l,int r,int x,int y,node* &t)
{
	if(t==nullptr) t=new node(inf);
	if(x==y) return t->t;
	if(l<=x && y<=r) return t->t;
	int m=(x+y)>>1;
	if(r<=m) return query(l,r,x,m,t->l);
	if(l>m) return query(l,r,m+1,y,t->r);
	return min(query(l,r,x,m,t->l),query(l,r,m+1,y,t->r)); 
}
node* g;
node* h;
int m,n;
int a[150000];
int b[150000];
int c[150000];
int d[150000];
long long int p[150000];
long long int t,r;
int main()
{
	scanf("%d %d",&m,&n);
	for(int i=0;i<m;i++) {
		scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
	}
	g=nullptr;
	insert(0,1,1,n,g);
	for(int i=0;i<m;i++) {
		p[i]=d[i]+query(a[i],b[i],1,n,g);
		insert(p[i],c[i],1,n,g);
	}
	h=nullptr;
	r=inf;
	insert(0,n,1,n,h);
	for(int i=0;i<m;i++) {
		t=d[i]+query(a[i],b[i],1,n,h);
		insert(t,c[i],1,n,h);
		r=min(r,t+p[i]-d[i]);
	}
	if(r>=inf) printf("-1");
	else printf("%lld",r);
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&m,&n);
  ~~~~~^~~~~~~~~~~~~~~
pinball.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49