답안 #68601 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68601	2018-08-17T13:49:34 Z	Kerim	Pinball (JOI14_pinball)	C++17	100 / 100	340 ms	48868 KB

pinball

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
vector<int>v;
const ll B=1e15;
struct tree{
	ll mn[MAXN<<2];
	tree(){		
		for(int i=0;i<MAXN*4;i++)
			mn[i]=B;
	}
	void upd(int p,ll v,int nd,int x,int y){
		if(x==y){
			umin(mn[nd],v);
			return;
		}
		int mid=(x+y)>>1;
		if(p<=mid)
			upd(p,v,nd<<1,x,mid);
		else
			upd(p,v,nd<<1|1,mid+1,y);
		mn[nd]=min(mn[nd<<1],mn[nd<<1|1]);	
	}
	ll tap(int l,int r,int nd,int x,int y){
		if(l>y or x>r)
			return B;
		if(l<=x and y<=r)
			return mn[nd];
		int mid=(x+y)>>1;
		return min(tap(l,r,nd<<1,x,mid),tap(l,r,nd<<1|1,mid+1,y));	
	}
}L,R;
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
int main(){
    //~ freopen("file.in", "r", stdin);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
		v.pb(c[i]);
	}
	v.pb(1);v.pb(m);sort(all(v));
	v.erase(unique(all(v)),v.end());int sz=v.size();
	L.upd(1,0,1,1,sz);
	R.upd(sz,0,1,1,sz);
	ll ans=B;
	for(int i=1;i<=n;i++){
		int pos=lower_bound(all(v),c[i])-v.begin()+1;
		int x=lower_bound(all(v),a[i])-v.begin()+1;
		int y=upper_bound(all(v),b[i])-v.begin();
		ll c1=L.tap(x,y,1,1,sz);
		ll c2=R.tap(x,y,1,1,sz);
		umin(ans,c1+c2+d[i]);
		L.upd(pos,c1+d[i],1,1,sz);
		R.upd(pos,c2+d[i],1,1,sz);
	}
	if(ans==B)
		ans=-1;
	printf("%lld\n",ans);	
	return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
pinball.cpp:55: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.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	6520 KB	Output is correct
2	Correct	8 ms	6632 KB	Output is correct
3	Correct	7 ms	6672 KB	Output is correct
4	Correct	7 ms	6788 KB	Output is correct
5	Correct	8 ms	6788 KB	Output is correct
6	Correct	7 ms	6964 KB	Output is correct
7	Correct	7 ms	6964 KB	Output is correct
8	Correct	9 ms	6964 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	6520 KB	Output is correct
2	Correct	8 ms	6632 KB	Output is correct
3	Correct	7 ms	6672 KB	Output is correct
4	Correct	7 ms	6788 KB	Output is correct
5	Correct	8 ms	6788 KB	Output is correct
6	Correct	7 ms	6964 KB	Output is correct
7	Correct	7 ms	6964 KB	Output is correct
8	Correct	9 ms	6964 KB	Output is correct
9	Correct	7 ms	6976 KB	Output is correct
10	Correct	8 ms	6976 KB	Output is correct
11	Correct	7 ms	7008 KB	Output is correct
12	Correct	9 ms	7032 KB	Output is correct
13	Correct	7 ms	7056 KB	Output is correct
14	Correct	8 ms	7056 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	6520 KB	Output is correct
2	Correct	8 ms	6632 KB	Output is correct
3	Correct	7 ms	6672 KB	Output is correct
4	Correct	7 ms	6788 KB	Output is correct
5	Correct	8 ms	6788 KB	Output is correct
6	Correct	7 ms	6964 KB	Output is correct
7	Correct	7 ms	6964 KB	Output is correct
8	Correct	9 ms	6964 KB	Output is correct
9	Correct	7 ms	6976 KB	Output is correct
10	Correct	8 ms	6976 KB	Output is correct
11	Correct	7 ms	7008 KB	Output is correct
12	Correct	9 ms	7032 KB	Output is correct
13	Correct	7 ms	7056 KB	Output is correct
14	Correct	8 ms	7056 KB	Output is correct
15	Correct	7 ms	7056 KB	Output is correct
16	Correct	9 ms	7136 KB	Output is correct
17	Correct	12 ms	7148 KB	Output is correct
18	Correct	9 ms	7188 KB	Output is correct
19	Correct	9 ms	7240 KB	Output is correct
20	Correct	9 ms	7240 KB	Output is correct
21	Correct	11 ms	7300 KB	Output is correct
22	Correct	8 ms	7332 KB	Output is correct
23	Correct	9 ms	7380 KB	Output is correct
24	Correct	9 ms	7420 KB	Output is correct

Subtask #4
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	6520 KB	Output is correct
2	Correct	8 ms	6632 KB	Output is correct
3	Correct	7 ms	6672 KB	Output is correct
4	Correct	7 ms	6788 KB	Output is correct
5	Correct	8 ms	6788 KB	Output is correct
6	Correct	7 ms	6964 KB	Output is correct
7	Correct	7 ms	6964 KB	Output is correct
8	Correct	9 ms	6964 KB	Output is correct
9	Correct	7 ms	6976 KB	Output is correct
10	Correct	8 ms	6976 KB	Output is correct
11	Correct	7 ms	7008 KB	Output is correct
12	Correct	9 ms	7032 KB	Output is correct
13	Correct	7 ms	7056 KB	Output is correct
14	Correct	8 ms	7056 KB	Output is correct
15	Correct	7 ms	7056 KB	Output is correct
16	Correct	9 ms	7136 KB	Output is correct
17	Correct	12 ms	7148 KB	Output is correct
18	Correct	9 ms	7188 KB	Output is correct
19	Correct	9 ms	7240 KB	Output is correct
20	Correct	9 ms	7240 KB	Output is correct
21	Correct	11 ms	7300 KB	Output is correct
22	Correct	8 ms	7332 KB	Output is correct
23	Correct	9 ms	7380 KB	Output is correct
24	Correct	9 ms	7420 KB	Output is correct
25	Correct	26 ms	7972 KB	Output is correct
26	Correct	64 ms	9364 KB	Output is correct
27	Correct	186 ms	12836 KB	Output is correct
28	Correct	158 ms	17004 KB	Output is correct
29	Correct	135 ms	18116 KB	Output is correct
30	Correct	285 ms	22856 KB	Output is correct
31	Correct	340 ms	26760 KB	Output is correct
32	Correct	337 ms	30656 KB	Output is correct
33	Correct	43 ms	30656 KB	Output is correct
34	Correct	119 ms	32260 KB	Output is correct
35	Correct	237 ms	37136 KB	Output is correct
36	Correct	327 ms	41008 KB	Output is correct
37	Correct	300 ms	44944 KB	Output is correct
38	Correct	255 ms	48868 KB	Output is correct

답안 #68601

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 18.0 / 18.0

Subtask #3 22.0 / 22.0

Subtask #4 49.0 / 49.0

Subtask #1
11.0 / 11.0

Subtask #2
18.0 / 18.0

Subtask #3
22.0 / 22.0

Subtask #4
49.0 / 49.0