oj.uz

Submission #36034

# Submission time Handle Problem Language Result Execution time Memory
36034 2017-12-04T09:42:27 Z Dat160601 Pinball (JOI14_pinball) C++14
100 / 100
 996 ms 33472 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(){
	ios_base::sync_with_stdio(0);
	cin>>m>>n;
	lw(1);
	lw(n);
	for(int i=1;i<=m;i++){
		cin>>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) cout<<-1;
	else cout<<ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 18352 KB Output is correct
2 Correct 133 ms 20196 KB Output is correct
3 Correct 413 ms 22696 KB Output is correct
4 Correct 213 ms 17420 KB Output is correct
5 Correct 286 ms 22168 KB Output is correct
6 Correct 373 ms 18352 KB Output is correct
7 Correct 719 ms 26244 KB Output is correct
8 Correct 646 ms 23620 KB Output is correct
9 Correct 76 ms 20460 KB Output is correct
10 Correct 353 ms 25452 KB Output is correct
11 Correct 453 ms 33472 KB Output is correct
12 Correct 996 ms 33472 KB Output is correct
13 Correct 796 ms 33472 KB Output is correct
14 Correct 793 ms 33472 KB Output is correct