Submission #738966

#	Time	Username	Problem	Language	Result	Execution time	Memory
738966		ThylOne	Stove (JOI18_stove)	C++14	100 / 100	62 ms	2384 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<pair<int,int>> delay;
	for(int i = 0 ; i < n-1;i++){
		delay.push_back({t[i+1]-t[i],i});
	}
	sort(delay.rbegin(),delay.rend());
	vector<int> indice;
	for(int i=0;i<min(n,k-1);i++){
		indice.push_back(delay[i].second);
	}
	sort(indice.begin(),indice.end());
	indice.push_back(n-1);
	int mini=-1;
	int ind=0;
	int score=0;
	for(int i = 0 ; i <n;i++){
		if(mini==-1){
			mini = t[i];
		}
		if(i==indice[ind]){
			ind++;
			score+=t[i]-mini+1;
			mini=-1;
		}
	}
	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: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50