Submission #738960

#	Time	Username	Problem	Language	Result	Execution time	Memory
738960		ThylOne	Stove (JOI18_stove)	C++14	0 / 100	2 ms	2260 KiB

stove

#include<bits/stdc++.h>


using namespace std;
using  ll = long long;
struct inter{
	int start;
	int end;
};
const int MAX_SIZE = (1<<18)+1;
const int LEAF = 1<<17;
pair<int,int> BT[MAX_SIZE];

pair<int,int> maxiPAIR(pair<int,int>a,pair<int,int>b){
	if(a.first>b.first){
		return a;
	}else{
		return b;
	}
}

void fillBT(vector<int> &a){
	for(int i = 0 ; i<MAX_SIZE;i++){
		BT[i] = {-1,-1};
	}
	for(int i = 0 ; i < a.size();i++){
		BT[i+LEAF] = {a[i],i};
	}
	for(int i = LEAF-1;i>=1;i--){
		BT[i] = maxiPAIR(BT[2*i],BT[2*i+1]);
	}
}

pair<int,int> requestMAX(int a,int b){
	if(a==b)return BT[a];
	if(a>b)return {-1,-1};
	if(a&1){
		return maxiPAIR(BT[a],requestMAX(a+1,b));
	}else if(!(b&1)){
		return maxiPAIR(BT[b],requestMAX(a,b-1));
	}else{
		return requestMAX(a/2,b/2);
	}
	
	
}
pair<int,int> maxiBT(int a,int b){
	return requestMAX(a+LEAF,b+LEAF);
}

bool operator<(inter const a,inter const b){
	return maxiBT(a.start,a.end-1).first>maxiBT(b.start,b.end-1).first;
}
int main(){
	int n,k;cin>>n>>k;
	vector<int> t(n);
	
	for(int i = 0 ; i < n ; i ++){
		cin>>t[i];
	}
	sort(t.begin(),t.end());
	vector<int> delay;
	for(int i = 0 ; i < n-1;i++){
		delay.push_back(t[i+1]-t[i]);
	}
	fillBT(delay);
	priority_queue<inter> PQ;
	PQ.push({0,n});
	int score = t[n-1]-t[0]+1;
	for(int i=0;i<k-1;i++){
		inter const&best = PQ.top();
		int pivot = maxiBT(best.start,best.end-1).second;
		score -= t[best.end]-t[best.start]+1;
		score += t[pivot]-t[best.start]+1;
		score += t[best.end]-t[pivot+1]+1;
		
		inter a = {best.start,pivot};
		inter b = {pivot+1,best.end};
		PQ.pop();
		PQ.push(a);
		PQ.push(b);
	}
	cout<<score<<endl;
	return 0;
}

Compilation message (stderr)

stove.cpp: In function 'void fillBT(std::vector<int>&)':
stove.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0 ; i < a.size();i++){
      |                  ~~^~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50