Submission #53878

#	Time	Username	Problem	Language	Result	Execution time	Memory
53878		milisav	Pinball (JOI14_pinball)	C++14	100 / 100	529 ms	36964 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;
vector<pair<int,int> > v;
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]);
		v.push_back(make_pair(a[i],i));
		v.push_back(make_pair(b[i],i+m));
		v.push_back(make_pair(c[i],i+2*m));
	}
	v.push_back(make_pair(1,-1));
	v.push_back(make_pair(n,-1));
	sort(v.begin(),v.end());
	int l=1;
	if(v[0].second!=-1) {
		if(v[0].second<m) a[v[0].second]=l;
		else {
			if(v[0].second<2*m) b[v[0].second-m]=l;
			else c[v[0].second-2*m]=l;
		}
	}
	for(int i=1;i<v.size();i++) {
		if(v[i].first>v[i-1].first) l++;
		if(v[i].second!=-1) {
			if(v[i].second<m) a[v[i].second]=l;
			else {
				if(v[i].second<2*m) b[v[i].second-m]=l;
				else c[v[i].second-2*m]=l;
			}
		}
	}
	n=l;
	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:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<v.size();i++) {
              ~^~~~~~~~~
pinball.cpp:46: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:48: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: 49 / 49