oj.uz

Submission #389832

# Submission time Handle Problem Language Result Execution time Memory
389832 2021-04-14T15:21:55 Z ogibogi2004 Pinball (JOI14_pinball) C++14
0 / 100
 7 ms 9680 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=2e15;
const int MAXM=1e5+6;
const int MAXA=3e5+6;
struct device
{
	ll row,a,b,c,d;
	bool operator<(device const& other)const
	{
		return c<other.c;
	}
};
device d[MAXM];
int n,m;
set<int>xs;
map<int,int>mp;
struct segment_tree
{
	ll tree[4*MAXA];
	void init()
	{
		for(int i=0;i<4*MAXA;i++)tree[i]=INF;
	}
	void update(int l,int r,int idx,int q,ll val)
	{
		if(l>q||r<q)return;
		if(l==r)
		{
			tree[idx]=min(tree[idx],val);
			return;
		}
		int mid=(l+r)/2;
		update(l,mid,idx*2,q,val);
		update(mid+1,r,idx*2+1,q,val);
		tree[idx]=min(tree[idx*2],tree[idx*2+1]);
	}
	ll query(int l,int r,int idx,int ql,int qr)
	{
		if(l>qr||r<ql)return INF;
		if(l>=ql&&r<=qr)return tree[idx];
		int mid=(l+r)/2;
		return min(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
	}
	ll query(ll l,ll r)
	{
		return query(1,MAXA,1,l,r);
	}
	void update(ll q,ll val)
	{
		update(1,MAXA,1,q,val);
	}
}t;
ll dp1[MAXM],dp2[MAXM];
int main()
{
	cin>>m>>n;
	for(int i=2;i<m+2;i++)
	{
		d[i].row=i;
		cin>>d[i].a>>d[i].b>>d[i].c>>d[i].d;
		xs.insert(d[i].a);
		xs.insert(d[i].b);
		xs.insert(d[i].c);
	}
	xs.insert(n);
	ll ans=INF;
	int cnt=0;
	for(auto xd:xs)
	{
		++cnt;
		mp[xd]=cnt;
	}
	n=mp[n];
	for(int i=2;i<m+2;i++)
	{
		d[i].a=mp[d[i].a];
		d[i].b=mp[d[i].b];
		d[i].c=mp[d[i].c];
	}
	t.init();
	for(int i=2;i<m+2;i++)
	{
		if(d[i].a==1)
		{
			dp1[i]=d[i].d;
		}
		else
		{
			dp1[i]=t.query(d[i].a,d[i].c)+d[i].d;
		}
		t.update(d[i].c,dp1[i]);
	}
	t.init();
	for(int i=2;i<m+2;i++)
	{
		if(d[i].b==n)
		{
			dp2[i]=d[i].d;
		}
		else
		{
			dp2[i]=t.query(d[i].c,d[i].b)+d[i].d;
		}
		t.update(d[i].c,dp2[i]);
	}
	for(int i=2;i<m+2;i++)
	{
		ans=min(ans,dp1[i]+dp2[i]-d[i].d);
	}
	if(ans==INF)cout<<"-1\n";
	else cout<<ans<<endl;
return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9680 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Incorrect 7 ms 9620 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9680 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Incorrect 7 ms 9620 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9680 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Incorrect 7 ms 9620 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9680 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Incorrect 7 ms 9620 KB Output isn't correct
8 Halted 0 ms 0 KB -