Submission #521997

#	Time	Username	Problem	Language	Result	Execution time	Memory
521997		MateGiorbelidze	K blocks (IZhO14_blocks)	C++14	0 / 100	3 ms	5016 KiB

blocks

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

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

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

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

ll find_max (ll v, ll tl, ll tr, ll l, ll r) {
	
	if (l > r) return 0;
	
	if (tl == l && tr == r) {
		
		return t[v] ;
		
	}
	
	ll m = (tl + tr) / 2;
		
	ll x = find_max (2 * v, tl , m , l , min (m , r)) ;
	
	ll y = find_max (2 * v + 1, m + 1 , tr , max(l , m + 1) , r) ;
	
	return max ( x , 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 = 1; i <= n; i++) {
		
		if (a[i] == mx) {
			
			d[i] = 1;
			
			break;
			
		}
		
	}
	
	
	for (int o = 2; o <= k; o++) {
		
		ans = 0; 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) {
					
					ll x = find_max(1 , 1 , n , l , i);
					
					if (x < mn) {
						
						ans = i; mn = x;
						
					}
					
					i++;
					
				}
			
			}
			else {
				
				while (i <= n) {
					
					ll x = find_max(1 , 1 , n , i , n);
					
					if (x < mn) {
						
						ans = i; mn = x;
						
					}
					
					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