Submission #95811

#	Time	Username	Problem	Language	Result	Execution time	Memory
95811		KLPP	Pinball (JOI14_pinball)	C++14	100 / 100	564 ms	166852 KiB

pinball

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define INF 1000000000000000
lld device[100000][4];
vector<int> clr;

class ST{
	lld arr[10000000];
	public:
	void init(int a, int b, int node){
		//cout<<a<<" "<<b<<endl;
		arr[node]=INF;
		if(a==b)return;
		int mid=(a+b)/2;
		init(a,mid,2*node);
		init(mid+1,b,2*node+1);
	}
	void update(int pos, lld val,int a, int b, int node){
		//cout<<a<<" "<<b<<" "<<node<<endl;
		if(pos<a || b<pos)return;
		arr[node]=min(arr[node],val);
		if(a==b)return;
		int mid=(a+b)/2;
		update(pos,val,a,mid,2*node);
		update(pos,val,mid+1,b,2*node+1);
	}
	lld query(int a, int b, int node, int x, int y){
		if(y<a || b<x)return INF;
		if(x<=a && b<=y)return arr[node];
		int mid=(a+b)/2;
		return min(query(a,mid,2*node,x,y),query(mid+1,b,2*node+1,x,y));
	}
	void print(int a, int b, int node){
		if(a==b){
			cout<<a<<" "<<arr[node]<<endl;
			return;
		}
		int mid=(a+b)/2;
		print(a,mid,2*node);
		print(mid+1,b,2*node+1);
	}
};
int main(){
	int m,n;
	cin>>m>>n;
	vector<int> table;
	table.push_back(0);
	table.push_back(n-1);
	for(int i=0;i<m;i++){
		cin>>device[i][0]>>device[i][1]>>device[i][2]>>device[i][3];
		for(int j=0;j<3;j++)device[i][j]--,table.push_back(device[i][j]);
	}
	sort(table.begin(),table.end());
	for(int i=0;i<table.size();i++){
		if(i==table.size()-1 || table[i]!=table[i+1]){
			clr.push_back(table[i]);
		}
	}//cout<<clr.size()<<endl;
	for(int i=0;i<m;i++){
		for(int j=0;j<3;j++){
			int lo,hi;
			lo=0;
			hi=clr.size()-1;
			while(hi-lo>0){
				int mid=(hi+lo)/2;
				if(clr[mid]==device[i][j]){
					hi=lo=mid;
				}
				if(clr[mid]>device[i][j]){
					hi=mid-1;
				}
				if(clr[mid]<device[i][j]){
					lo=mid+1;
				}
			}
			device[i][j]=lo;
			//cout<<lo<<" ";
		}//cout<<endl;
	}
	n=clr.size();
	ST *L,*R;
	L=new ST();
	R=new ST();
	L->init(0,n-1,1);
	R->init(0,n-1,1);
	L->update(0,0,0,n-1,1);
	R->update(n-1,0,0,n-1,1);
	lld ans=INF;
	for(int i=0;i<m;i++){
		//cout<<device[i][0]<<" "<<device[i][1]<<" "<<device[i][2]<<endl;
		/*for(int j=device[i][0];j<=device[i][1];j++){
			DPL[device[i][2]]=min(DPL[device[i][2]],DPL[j]+device[i][3]);
			DPR[device[i][2]]=min(DPR[device[i][2]],DPR[j]+device[i][3]);
		}*/
		//print(0,n-1,1);
		lld VL=L->query(0,n-1,1,device[i][0],device[i][1]);
		lld VR=R->query(0,n-1,1,device[i][0],device[i][1]);
		ans=min(ans,VL+VR+device[i][3]);
		L->update(device[i][2],VL+device[i][3],0,n-1,1);
		R->update(device[i][2],VR+device[i][3],0,n-1,1);
		
		/*cout<<i<<endl;
		for(int j=0;j<n;j++){
			cout<<DPL[j]<<" "<<DPR[j]<<endl;
		}*/
		/*for(int j=device[i][0];j<=device[i][1];j++){
			for(int k=device[i][0];k<=device[i][1];k++){
				
				ans=min(ans,DPL[j]+DPR[k]+device[i][3]);
					//cout<<i<<" "<<j<<" "<<k<<endl;
				
			}
		}*/
	}
	if(ans!=INF)cout<<ans<<endl;
	else cout<<-1<<endl;
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<table.size();i++){
              ~^~~~~~~~~~~~~
pinball.cpp:57:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i==table.size()-1 || table[i]!=table[i+1]){
      ~^~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49