Submission #841701

#	Time	Username	Problem	Language	Result	Execution time	Memory
841701		MinaRagy06	K blocks (IZhO14_blocks)	C++17	0 / 100	1038 ms	2396 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define endl    '\n'
#define ll      long long
#define md      ((l + r) >> 1)
#pragma GCC optimize("Ofast,O3")

const int BUF_SZ = 1 << 20;
 
inline namespace Input {
char buf[BUF_SZ];
int pos;
int len;
char next_char() {
	if (pos == len) {
		pos = 0;
		len = (int)fread(buf, 1, BUF_SZ, stdin);
		if (!len) {
			return EOF;
		}
	}
	return buf[pos++];
}
 
int read_int() {
	int x;
	char ch;
	int sgn = 1;
	while (!isdigit(ch = next_char())) {
		if (ch == '-') {
			sgn *= -1;
		}
	}
	x = ch - '0';
	while (isdigit(ch = next_char())) {
		x = x * 10 + (ch - '0');
	}
	return x * sgn;
}
long long read_ll() {
	long long x;
	char ch;
	int sgn = 1;
	while (!isdigit(ch = next_char())) {
		if (ch == '-') {
			sgn *= -1;
		}
	}
	x = ch - '0';
	while (isdigit(ch = next_char())) {
		x = x * 10 + (ch - '0');
	}
	return x * sgn;
}
} // namespace Input
inline namespace Output {
char buf[BUF_SZ];
int pos;
 
void flush_out() {
	fwrite(buf, 1, pos, stdout);
	pos = 0;
}
 
void write_char(char c) {
	if (pos == BUF_SZ) {
		flush_out();
	}
	buf[pos++] = c;
}
 
void write_int(long long x) {
	static char num_buf[100];
	if (x < 0) {
		write_char('-');
		x *= -1;
	}
	int len = 0;
	for (; x >= 10; x /= 10) {
		num_buf[len++] = (char)('0' + (x % 10));
	}
	write_char((char)('0' + x));
	while (len) {
		write_char(num_buf[--len]);
	}
	write_char('\n');
}
 
// auto-flush output when program exits
void init_output() { assert(atexit(flush_out) == 0); }
} // namespace Output


ll dp[2][100'005];
int a[100'005], sparse[17][100'005], lg[100'005];
void build(int n)
{
    for (int i = 1; i <= n; i++) sparse[0][i] = a[i];
    for (int j = 1; j < 17; j++) for (int i = 1; i + (1 << (j - 1)) <= n; i++) sparse[j][i] = max(sparse[j-1][i], sparse[j-1][i + (1 << (j - 1))]);
}
int query(int l, int r)
{
    int sz = lg[r-l+1];
    return max(sparse[sz][l], sparse[sz][r-(1 << sz) + 1]);
}
int n, m;
int mstanyeh(int lvl, int j, int k)
{
    if (dp[lvl & 1][j] - dp[lvl & 1][k] > query(k + 1, n) - query(j + 1, n)) return n + 1;
    int l = max(j + 1, k + 1), r = n;
    while (l <= r)
    {
        dp[lvl & 1][j] - dp[lvl & 1][k] <= query(k + 1, md) - query(j + 1, md)? r = md - 1 : l = md + 1;
    }
    return l;
}
int v[100'005], mstany[100'005], vsz, mstanysz, val;
signed main()
{
    init_output();
    lg[1] = 0;
    for (int i = 2; i < 100'005; i++) lg[i] = lg[i >> 1] + 1;
    int t = read_int(), st = read_int();
    while (t--)
    {
        n = read_int(), m = read_int();
        for (int i = 1; i <= n; i++) a[i] = read_int();
        build(n);
        for (int i = 1; i <= n; i++) dp[0][i] = query(1, i);
        dp[0][0] = dp[1][0] = 1e18;
        for (int i = 1; i < m; i++)
        {
            vsz = mstanysz = 0;
            for (int j = 1; j <= n; j++)
            {
                while (vsz > 1 && mstany[mstanysz-1] <= (val = mstanyeh(i - 1, v[vsz-1], j - 1))) vsz--, mstanysz--;
                if (vsz == 1) val = mstanyeh(i - 1, v[vsz-1], j - 1);
                v[vsz++] = j - 1;
                if (vsz > 1) mstany[mstanysz++] = val;
                while (vsz > 1 && mstany[mstanysz-1] <= j) vsz--, mstanysz--;
                dp[i&1][j] = dp[(i - 1)&1][v[vsz-1]] + query(v[vsz-1] + 1, j);
            }
        }
        write_int(dp[(m - 1) & 1][n]);
    }
    return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:123:25: warning: unused variable 'st' [-Wunused-variable]
  123 |     int t = read_int(), st = read_int();
      |                         ^~

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