oj.uz

Submission #95811

# Submission time Handle Problem Language Result Execution time Memory
95811 2019-02-02T17:41:56 Z KLPP Pinball (JOI14_pinball) C++14
100 / 100
 564 ms 166852 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 156920 KB Output is correct
2 Correct 117 ms 156920 KB Output is correct
3 Correct 119 ms 156888 KB Output is correct
4 Correct 122 ms 156920 KB Output is correct
5 Correct 124 ms 156920 KB Output is correct
6 Correct 116 ms 156844 KB Output is correct
7 Correct 104 ms 156844 KB Output is correct
8 Correct 104 ms 156916 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 156920 KB Output is correct
2 Correct 117 ms 156920 KB Output is correct
3 Correct 119 ms 156888 KB Output is correct
4 Correct 122 ms 156920 KB Output is correct
5 Correct 124 ms 156920 KB Output is correct
6 Correct 116 ms 156844 KB Output is correct
7 Correct 104 ms 156844 KB Output is correct
8 Correct 104 ms 156916 KB Output is correct
9 Correct 124 ms 156940 KB Output is correct
10 Correct 125 ms 156932 KB Output is correct
11 Correct 121 ms 156920 KB Output is correct
12 Correct 122 ms 156920 KB Output is correct
13 Correct 126 ms 156832 KB Output is correct
14 Correct 124 ms 156832 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 156920 KB Output is correct
2 Correct 117 ms 156920 KB Output is correct
3 Correct 119 ms 156888 KB Output is correct
4 Correct 122 ms 156920 KB Output is correct
5 Correct 124 ms 156920 KB Output is correct
6 Correct 116 ms 156844 KB Output is correct
7 Correct 104 ms 156844 KB Output is correct
8 Correct 104 ms 156916 KB Output is correct
9 Correct 124 ms 156940 KB Output is correct
10 Correct 125 ms 156932 KB Output is correct
11 Correct 121 ms 156920 KB Output is correct
12 Correct 122 ms 156920 KB Output is correct
13 Correct 126 ms 156832 KB Output is correct
14 Correct 124 ms 156832 KB Output is correct
15 Correct 122 ms 156824 KB Output is correct
16 Correct 122 ms 156920 KB Output is correct
17 Correct 110 ms 156920 KB Output is correct
18 Correct 113 ms 156924 KB Output is correct
19 Correct 186 ms 157020 KB Output is correct
20 Correct 125 ms 156920 KB Output is correct
21 Correct 127 ms 156908 KB Output is correct
22 Correct 110 ms 157048 KB Output is correct
23 Correct 107 ms 157012 KB Output is correct
24 Correct 106 ms 156924 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 156920 KB Output is correct
2 Correct 117 ms 156920 KB Output is correct
3 Correct 119 ms 156888 KB Output is correct
4 Correct 122 ms 156920 KB Output is correct
5 Correct 124 ms 156920 KB Output is correct
6 Correct 116 ms 156844 KB Output is correct
7 Correct 104 ms 156844 KB Output is correct
8 Correct 104 ms 156916 KB Output is correct
9 Correct 124 ms 156940 KB Output is correct
10 Correct 125 ms 156932 KB Output is correct
11 Correct 121 ms 156920 KB Output is correct
12 Correct 122 ms 156920 KB Output is correct
13 Correct 126 ms 156832 KB Output is correct
14 Correct 124 ms 156832 KB Output is correct
15 Correct 122 ms 156824 KB Output is correct
16 Correct 122 ms 156920 KB Output is correct
17 Correct 110 ms 156920 KB Output is correct
18 Correct 113 ms 156924 KB Output is correct
19 Correct 186 ms 157020 KB Output is correct
20 Correct 125 ms 156920 KB Output is correct
21 Correct 127 ms 156908 KB Output is correct
22 Correct 110 ms 157048 KB Output is correct
23 Correct 107 ms 157012 KB Output is correct
24 Correct 106 ms 156924 KB Output is correct
25 Correct 130 ms 157736 KB Output is correct
26 Correct 186 ms 159468 KB Output is correct
27 Correct 350 ms 163364 KB Output is correct
28 Correct 390 ms 165152 KB Output is correct
29 Correct 280 ms 161868 KB Output is correct
30 Correct 447 ms 165324 KB Output is correct
31 Correct 538 ms 166852 KB Output is correct
32 Correct 509 ms 166160 KB Output is correct
33 Correct 185 ms 158840 KB Output is correct
34 Correct 301 ms 161732 KB Output is correct
35 Correct 433 ms 166444 KB Output is correct
36 Correct 564 ms 166392 KB Output is correct
37 Correct 497 ms 166428 KB Output is correct
38 Correct 458 ms 166392 KB Output is correct