Submission #166391

#	Time	Username	Problem	Language	Result	Execution time	Memory
166391		Trickster	K개의 묶음 (IZhO14_blocks)	C++14	Compilation error	0 ms	0 KiB

blocks

//Suleyman Atayew

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>

#define N 100010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define inf 1000000007
#define pii pair <int, int>

using namespace std;

int n, k;
int v[N];
int MX[N];
int T[N*4];
int L[N*4];
int dp[110][N];

void init(int l, int r, int node)
{
	L[node] = 0;
	T[node] = 1e9;
	
	if(l == r) return;
	
	init(l, (l+r)/2, node*2);
	init((l+r)/2+1, r, node*2+1);
}

void upd2(int x, int y, int l, int r, int node)
{
	if(l == r) {
		T[node] = dp[x][l];
		return;
	}
	
	if(y <= (l+r)/2)
		upd2(x, y, l, (l+r)/2, node*2);
	else
		upd2(x, y, (l+r)/2+1, r, node*2+1);
	
	T[node] = min(T[node*2], T[node*2+1]);
	
	if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
	else L[node] = L[node*2+1];
}
shift(int node, int to)
{
	T[to] -= L[to];
	T[to] += L[node];
	L[to] = L[node];
}
void upd(int a, int b, int x, int l, int r, int node)
{
	if(l > b || r < a) return;
	
	if(l >= a && r <= b) {
		if(l == r) {
			T[node] -= L[node];
			T[node] += x;
			L[node] = x;
			return;
		}
		
		L[node] = x;
		
		shift(node, node*2);
		shift(node, node*2+1);
		
		T[node] = min(T[node*2], T[node*2+1]);
		
		if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
		else L[node] = L[node*2+1];
		
		return;
	}
	
	shift(node, node*2);
	shift(node, node*2+1);
	L[node] = 0;
	
	upd(a, b, x, l, (l+r)/2, node*2);
	upd(a, b, x, (l+r)/2+1, r, node*2+1);
	
	T[node] = min(T[node*2], T[node*2+1]);
	
	if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
	else L[node] = L[node*2+1];
}

int main()
{
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++)
		cin >> v[i];
	
	vector <int> E;
	for(int i = 1; i <= n; i++) {
		while(!E.empty() && v[E.back()] < v[i])
			E.pop_back();
		
		if(E.empty()) MX[i] = 0;
		else {
			if(v[E.back()] == v[i]) MX[i] = MX[E.back()];
			else MX[i] = E.back()+1;
		}
		
		E.pb(i);
	}
	
	for(int i = 1; i <= n; i++) dp[0][i] = 1e9;
	
	
	for(int i = 1; i <= k; i++) {
		init(0, n, 1);
		
		for(int h = 0; h <= n; h++) {
			if(h < i) {
				dp[i][h] = 1e9;
				
				upd2(i-1, h, 0, n, 1);
				
				continue;
			}
			
			upd(MX[h], h-1, v[h], 0, n, 1);
			
			dp[i][h] = T[1];
			
//			cout << T[1] << " ------------\n";
//			
//			if(i == 2) {
//				for(int h = 1; h <= 13; h++) cout << T[h] << " " << L[h] << "\n";
//				cout << "\n";
//			}
			
			upd2(i-1, h, 0, n, 1);
			
//			if(i == 2) {
//				for(int h = 1; h <= 13; h++) cout << T[h] << " " << L[h] << "\n";
//				cout << "\n";
//			}
		}
	}
	
	cout << dp[k][n];
}

Compilation message (stderr)

blocks.cpp:58:23: error: ISO C++ forbids declaration of 'shift' with no type [-fpermissive]
 shift(int node, int to)
                       ^
blocks.cpp: In function 'int shift(int, int)':
blocks.cpp:63:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^