Submission #522026

#	Time	Username	Problem	Language	Result	Execution time	Memory
522026		MateGiorbelidze	K blocks (IZhO14_blocks)	C++14	0 / 100	6 ms	8140 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define pll pair<ll,ll>
#define sc second
#define vc vector

ll n , k , mx , mn = 1000001 , ans;

vc <pll> t(400001);
vc <ll> a(100001) , d(100001);

void build (ll v, ll tl, ll tr) {
	
	if (tl == tr) {
		
		t[v].ff = a[tl];
		
		t[v].sc = tl;
		
	}
	else {
		
		ll m = (tl + tr) / 2;
		
		build (2 * v, tl , m) ;
		
		build (2 * v + 1, m + 1 , tr) ;
		
		if ( t[2 * v].ff > t[2 * v + 1].ff ) {
			
			t[v].ff = t[2 * v].ff;
			
			t[v].sc = t[2 * v].sc;
			
		}
		else {
			
			t[v].ff = t[2 * v + 1].ff;
			
			t[v].sc = t[2 * v + 1].sc;
			
		}
		
	}
	
}

pll find_max (ll v, ll tl, ll tr, ll l, ll r) {
	
	if (l > r) return {0 , 0};
	
	if (tl == l && tr == r) {
		
		return t[v] ;
		
	}
	
	ll m = (tl + tr) / 2;
		
	pll x = find_max (2 * v, tl , m , l , min (m , r)) ;
	
	pll y = find_max (2 * v + 1, m + 1 , tr , max(l , m + 1) , r) ;
	
	if ( x.ff > y.ff ) {
			
		return x;
		
	}
	else 				{
		
		return y;
		
	}
	
}

int main () {
	
	cin>>n>>k;
	
	for (int i = 1; i <= n; i++){
		cin>>a[i];
		mx = max (mx , a[i]) ;
	}
		
	build (1 , 1 , n) ;
		
	for (int i = n; i >= 1; i--) {
		
		if (a[i] == mx) {
			
			d[i] = 1;
			
			break;
			
		}
		
	}
	
	
	for (int o = 2; o <= k; o++) {
		
		ans = 0; mn = 1000001 ; ll cnt = 0 , l = 1;
	
		for (int i = 1; i <= n; i++) {
			
			if (d[i] == 1) {
				
				cnt++;
				
				l = i + 1;
				
				continue;
				
			}
			
			if (cnt != o - 1) {
			
				while (d[i] != 1) {
					
					pll x = find_max(1 , 1 , n , l , i);
					
					if (x.ff < mn) {
						
						ans = x.sc; mn = x.ff;
						
					}
					
					i++;
					
				}
			
			}
			else {
				
				while (i <= n) {
					
					pll x = find_max(1 , 1 , n , i , n);
					
					if (x.ff < mn) {
						
						ans = x.sc; mn = x.ff;
						
					}
					
					i++;
					
				}
				
			}
			
			i--;
			
		}
		
		d[ans] = 1;
	
	}
	
	ll s = 0;
	
	for (int i = 1; i <= n; i++) {
		
		if (d[i] == 1) {
			
			s += a[i];
			
			
			
		}
		
	}
	
	cout<<s;
	
}

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