oj.uz

Submission #36035

# Submission time Handle Problem Language Result Execution time Memory
36035 2017-12-04T09:44:28 Z Dat160601 Pinball (JOI14_pinball) C++14
100 / 100
 946 ms 33332 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int m,n;
const int N=1e5+7;
int lef[N],rig[N],md[N];
long long cost[N],costleft[N],costright[N],it[15*N],ans=1e15;
map <int,int> vis;
vector <int> val;
void lw(int x){
	vis[x]++;
	if(vis[x]==1) val.pb(x);
}
void init(int k,int l,int r){
	if(l==r){
		it[k]=1e15;
		return;
	}
	int mid=(l+r)/2;
	init(k*2,l,mid);
	init(k*2+1,mid+1,r);
	it[k]=1e15;
}
void upd(int k,int l,int r,int pos,long long vl){
	if(l>pos || r<pos || l>r) return;
	if(l==r && l==pos){
		it[k]=min(it[k],vl);
		return;
	}
	int mid=(l+r)/2;
	upd(k*2,l,mid,pos,vl);
	upd(k*2+1,mid+1,r,pos,vl);
	it[k]=min(it[k*2],it[k*2+1]);
}
long long get(int k,int l,int r,int L,int R){
	if(l>R || r<L || l>r) return 1e15;
	if(l>=L && r<=R) return it[k];
	int mid=(l+r)/2;
	return min(get(k*2,l,mid,L,R),get(k*2+1,mid+1,r,L,R));
}
int main(){
	scanf("%d %d",&m,&n);
	lw(1);
	lw(n);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d %lld",&lef[i],&rig[i],&md[i],&cost[i]);
		lw(lef[i]);
		lw(rig[i]);
		lw(md[i]);
	}
	sort(val.begin(),val.end());
	int cnt=0;
	for(auto x:val){
		cnt++;
		vis[x]=cnt;
	}
	for(int i=1;i<=m;i++){
		lef[i]=vis[lef[i]];
		rig[i]=vis[rig[i]];
		md[i]=vis[md[i]];
	}
	init(1,1,cnt);
	for(int i=1;i<=m;i++){
		costleft[i]=get(1,1,cnt,lef[i],rig[i]);
		if(lef[i]==1) costleft[i]=0;
		//cout<<costleft[i]<<endl;
		upd(1,1,cnt,md[i],costleft[i]+cost[i]);
	}
	init(1,1,cnt);
	for(int i=1;i<=m;i++){
		costright[i]=get(1,1,cnt,lef[i],rig[i]);
		if(rig[i]==cnt) costright[i]=0;
		ans=min(ans,costleft[i]+costright[i]+cost[i]);
		upd(1,1,cnt,md[i],costright[i]+cost[i]);
	}
	if(ans==1e15) printf("-1");
	else printf("%lld",ans);
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:42:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&m,&n);
                      ^
pinball.cpp:46:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %lld",&lef[i],&rig[i],&md[i],&cost[i]);
                                                         ^

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17260 KB Output is correct
2 Correct 0 ms 17260 KB Output is correct
3 Correct 3 ms 17396 KB Output is correct
4 Correct 0 ms 17260 KB Output is correct
5 Correct 3 ms 17396 KB Output is correct
6 Correct 0 ms 17392 KB Output is correct
7 Correct 0 ms 17396 KB Output is correct
8 Correct 3 ms 17396 KB Output is correct
9 Correct 3 ms 17396 KB Output is correct
10 Correct 3 ms 17396 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 18212 KB Output is correct
2 Correct 146 ms 20188 KB Output is correct
3 Correct 429 ms 22556 KB Output is correct
4 Correct 243 ms 17396 KB Output is correct
5 Correct 346 ms 22028 KB Output is correct
6 Correct 383 ms 18212 KB Output is correct
7 Correct 926 ms 26104 KB Output is correct
8 Correct 639 ms 23480 KB Output is correct
9 Correct 83 ms 20320 KB Output is correct
10 Correct 366 ms 25312 KB Output is correct
11 Correct 479 ms 33332 KB Output is correct
12 Correct 946 ms 33332 KB Output is correct
13 Correct 846 ms 33332 KB Output is correct
14 Correct 849 ms 33332 KB Output is correct