oj.uz

Submission #389840

# Submission time Handle Problem Language Result Execution time Memory
389840 2021-04-14T15:36:57 Z ogibogi2004 Pinball (JOI14_pinball) C++14
51 / 100
 1000 ms 4908 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;
	for(int i=2;i<m+2;i++)
	{
		if(d[i].a==1)dp1[i]=d[i].d;
		else
		{
			dp1[i]=INF;
			for(int j=i-1;j>=2;j--)
			{
				if(d[j].c>=d[i].a&&d[j].c<=d[i].b)
				{
					dp1[i]=min(dp1[i],dp1[j]+d[i].d);
				}
			}
		}
	}
	for(int i=2;i<m+2;i++)
	{
		if(d[i].b==n)dp2[i]=d[i].d;
		else
		{
			dp2[i]=INF;
			for(int j=i-1;j>=2;j--)
			{
				if(d[j].c>=d[i].a&&d[j].c<=d[i].b)
				{
					dp2[i]=min(dp2[i],dp2[j]+d[i].d);
				}
			}
		}
		ans=min(ans,dp1[i]+dp2[i]-d[i].d);
	}
	if(ans<INF)cout<<ans<<endl;
	else cout<<"-1\n";
	/*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].b)+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].a,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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 8 ms 452 KB Output is correct
18 Correct 7 ms 332 KB Output is correct
19 Correct 8 ms 460 KB Output is correct
20 Correct 8 ms 460 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 7 ms 460 KB Output is correct
23 Correct 5 ms 460 KB Output is correct
24 Correct 6 ms 460 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 8 ms 452 KB Output is correct
18 Correct 7 ms 332 KB Output is correct
19 Correct 8 ms 460 KB Output is correct
20 Correct 8 ms 460 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 7 ms 460 KB Output is correct
23 Correct 5 ms 460 KB Output is correct
24 Correct 6 ms 460 KB Output is correct
25 Correct 536 ms 1912 KB Output is correct
26 Execution timed out 1086 ms 4908 KB Time limit exceeded
27 Halted 0 ms 0 KB -