제출 #392922

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

blocks

#include <iostream>
#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);
		}
	}
	int query(int L, int D, int x, int l, int d){
		propagate(x);
		if(L>=l && D<=d){
			return t[x];
		}
		int lijeva=1e9, desna=1e9;
		if((L+D)/2>=l){
			lijeva=query(L, (L+D)/2, x*2, l, d);
		}
		if((L+D)/2+1<=d){
			desna=query((L+D)/2+1, D, x*2+1, l, d);
		}
		return min(lijeva, desna);
	}
};

struct logaritamska{
	int l[maxn];
	void update(int x, int val){
		for(; x<maxn; x+=(x & -x)){
			l[x]=max(l[x], val);
		}
	}
	int query(int x){
		int sol=0;
		for(; x>0; x-=(x & -x)){
			sol=max(sol, l[x]);
		}
		return sol;
	}
};

tournament T[maxk];
logaritamska L;
int n, k;


int rijesi(int x, int pos){
	int rev=maxn-pos;
	int lo=rev, hi=maxn-1, mid;
	while(lo<hi){
		mid=(lo+hi)/2+1;
		if(L.query(mid)<x){
			lo=mid;
		}
		else{
			hi=mid-1;
		}
	}
	L.update(rev, x);
	return maxn-lo;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	int a;
	int pos;
	int maksi=0;
	for(int i=0; i<n; i++){
		cin >> a;
		maksi=max(maksi, a);
		pos=rijesi(a, i+1)-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){
		cout << maksi <<  '\n';
	}
	else{
		cout << T[k].mindp[n+pot] << '\n';
	}
}

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