oj.uz

Submission #36033

# Submission time Handle Problem Language Result Execution time Memory
36033 2017-12-04T09:39:55 Z Dat160601 Pinball (JOI14_pinball) C++14
18 / 100
 486 ms 22696 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]=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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 17420 KB Output isn't correct
2 Halted 0 ms 0 KB -

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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 17420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 18352 KB Output is correct
2 Correct 146 ms 20196 KB Output is correct
3 Correct 486 ms 22696 KB Output is correct
4 Incorrect 219 ms 17420 KB Output isn't correct
5 Halted 0 ms 0 KB -