제출 #392929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
392929		vanic	K개의 묶음 (IZhO14_blocks)	C++14	53 / 100	1105 ms	229884 KiB

blocks

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=1e5+5, Log=17, pot=(1<<Log), maxk=105;
const int inf=1e9;

struct tournament{
	int t[pot*2];
	int mindp[pot*2];
	int prop[pot*2];
	tournament(){
		for(int i=0; i<pot*2; i++){
			t[i]=inf;
			mindp[i]=inf;
		}
	}
	void propagate(int x){
		if(!prop[x]){
			return;
		}
		t[x]=prop[x]+mindp[x];
		if(x<pot){
			prop[x*2]=prop[x];
			prop[x*2+1]=prop[x];
		}
		prop[x]=0;
	}
	void update0(int x, int val){
		mindp[x]=val;
		for(x/=2; x>0; x/=2){
			mindp[x]=min(mindp[x*2], mindp[x*2+1]);
		}
	}
	void update(int x, int val){
		t[x]=mindp[x]+val;
		for(x/=2; x>0; x/=2){
			propagate(x*2);
			propagate(x*2+1);
			t[x]=min(t[x*2], t[x*2+1]);
		}
	}
	void update2(int L, int D, int x, int l, int d, int val){
		propagate(x);
		if(L>=l && D<=d){
			update(x, val);
			if(x<pot){
				prop[x*2]=val;
				prop[x*2+1]=val;
			}
			return;
		}
		if((L+D)/2>=l){
			update2(L, (L+D)/2, x*2, l, d, val);
		}
		if((L+D)/2+1<=d){
			update2((L+D)/2+1, D, x*2+1, l, d, val);
		}
	}
};


tournament T[maxk];
int n, k;

vector < pair < int, int > > v;


int main(){
	scanf("%d%d", &n, &k);
	int a;
	int pos;
	int maksi=0;
	v.push_back({inf, 0});
	for(int i=0; i<n; i++){
		scanf("%d", &a);
		maksi=max(maksi, a);
		while(v.back().first<a){
			v.pop_back();
		}
		pos=v.back().second;
		v.push_back({a, i+1});
//		cout << pos << endl;
		T[1].update0(i+1+pot, maksi);
		for(int j=2; j<=k; j++){
			if(j>i+1){
				break;
			}
			else{
//				cout << "uso " << i << ' ' << j << endl;
				T[j-1].update2(0, pot-1, 1, pos, i, a);
//				cout << T[j-1].query(0, pot-1, 1, pos, i) << endl;
				T[j].update0(i+pot+1, T[j-1].t[1]);
			}
		}
	}
	if(k==1){
		printf("%d\n", maksi);
	}
	else{
		printf("%d\n", T[k].mindp[n+pot]);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

blocks.cpp: In function 'int main()':
blocks.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
blocks.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |   scanf("%d", &a);
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 0 / 47