This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
* ___
* _ / _\_
* / | |___|
* | | |
* \_| __ |
* \_/ \_/
* uwu amogus
*/
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x7FFFFFFF
#define llinf 0x7FFFFFFFFFFFFFFF
#define ff first
#define ss second
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a - 1; i >= b; i--)
//#define assert void
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#define int ll
#ifndef __OY_FASTIO__
#define __OY_FASTIO__
#define cin OY::IO::InputHelper::get_instance()
#define cout OY::IO::OutputHelper::get_instance()
#define endl '\n'
namespace OY {
namespace IO {
using size_type = size_t;
static constexpr size_type INPUT_BUFFER_SIZE = 1 << 16, OUTPUT_BUFFER_SIZE = 1 << 16, MAX_INTEGER_SIZE = 20, MAX_FLOAT_SIZE = 50;
#ifdef OY_LOCAL
static constexpr char input_file[] = "in.txt", output_file[] = "out.txt";
#else
static constexpr char input_file[] = "", output_file[] = "";
#endif
struct InputHelper {
FILE *m_file_ptr;
char m_buf[INPUT_BUFFER_SIZE], *m_end, *m_cursor;
bool m_ok;
InputHelper &set_bad() { return m_ok = false, *this; }
template <size_type BlockSize>
void _reserve() {
size_type a = m_end - m_cursor;
if (a >= BlockSize) return;
memmove(m_buf, m_cursor, a), m_cursor = m_buf;
size_type b = a + fread(m_buf + a, 1, INPUT_BUFFER_SIZE - a, m_file_ptr);
if (b < INPUT_BUFFER_SIZE) m_end = m_buf + b, *m_end = EOF;
}
template <typename Tp, typename BinaryOperation>
InputHelper &fill_integer(Tp &ret, BinaryOperation op) {
if (!isdigit(*m_cursor)) return set_bad();
ret = op(Tp(0), *m_cursor - '0');
size_type len = 1;
while (isdigit(*(m_cursor + len))) ret = op(ret * 10, *(m_cursor + len++) - '0');
m_cursor += len;
return *this;
}
explicit InputHelper(const char *inputFileName) : m_ok(true), m_cursor(m_buf + INPUT_BUFFER_SIZE), m_end(m_buf + INPUT_BUFFER_SIZE) { m_file_ptr = *inputFileName ? fopen(inputFileName, "rt") : stdin; }
~InputHelper() { fclose(m_file_ptr); }
static InputHelper &get_instance() {
static InputHelper s_obj(input_file);
return s_obj;
}
static bool is_blank(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }
static bool is_endline(char c) { return c == '\n' || c == EOF; }
const char &getchar_checked() {
_reserve<1>();
return *m_cursor;
}
const char &getchar_unchecked() const { return *m_cursor; }
void next() { ++m_cursor; }
template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &num) {
while (is_blank(getchar_checked())) next();
_reserve<MAX_INTEGER_SIZE>();
if (getchar_unchecked() != '-') return fill_integer(num, std::plus<Tp>());
next();
return fill_integer(num, std::minus<Tp>());
}
template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &num) {
while (is_blank(getchar_checked())) next();
_reserve<MAX_INTEGER_SIZE>();
return fill_integer(num, std::plus<Tp>());
}
template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &num) {
bool neg = false, integer = false, decimal = false;
while (is_blank(getchar_checked())) next();
_reserve<MAX_FLOAT_SIZE>();
if (getchar_unchecked() == '-') {
neg = true;
next();
}
if (!isdigit(getchar_unchecked()) && getchar_unchecked() != '.') return set_bad();
if (isdigit(getchar_unchecked())) {
integer = true;
num = getchar_unchecked() - '0';
while (next(), isdigit(getchar_unchecked())) num = num * 10 + (getchar_unchecked() - '0');
}
if (getchar_unchecked() == '.')
if (next(), isdigit(getchar_unchecked())) {
if (!integer) num = 0;
decimal = true;
Tp unit = 0.1;
num += unit * (getchar_unchecked() - '0');
while (next(), isdigit(getchar_unchecked())) num += (unit *= 0.1) * (getchar_unchecked() - '0');
}
if (!integer && !decimal) return set_bad();
if (neg) num = -num;
return *this;
}
InputHelper &operator>>(char &c) {
while (is_blank(getchar_checked())) next();
if (getchar_checked() == EOF) return set_bad();
c = getchar_checked(), next();
return *this;
}
InputHelper &operator>>(std::string &s) {
while (is_blank(getchar_checked())) next();
if (getchar_checked() == EOF) return set_bad();
s.clear();
do {
s += getchar_checked();
next();
} while (!is_blank(getchar_checked()) && getchar_unchecked() != EOF);
return *this;
}
explicit operator bool() { return m_ok; }
};
struct OutputHelper {
FILE *m_file_ptr = nullptr;
char m_buf[OUTPUT_BUFFER_SIZE], *m_end, *m_cursor;
char m_temp_buf[MAX_FLOAT_SIZE], *m_temp_buf_cursor, *m_temp_buf_dot;
uint64_t m_float_reserve, m_float_ratio;
void _write() { fwrite(m_buf, 1, m_cursor - m_buf, m_file_ptr), m_cursor = m_buf; }
template <size_type BlockSize>
void _reserve() {
size_type a = m_end - m_cursor;
if (a >= BlockSize) return;
_write();
}
OutputHelper(const char *outputFileName, size_type prec = 6) : m_cursor(m_buf), m_end(m_buf + OUTPUT_BUFFER_SIZE), m_temp_buf_cursor(m_temp_buf) { m_file_ptr = *outputFileName ? fopen(outputFileName, "wt") : stdout, precision(prec); }
static OutputHelper &get_instance() {
static OutputHelper s_obj(output_file);
return s_obj;
}
~OutputHelper() { flush(), fclose(m_file_ptr); }
void precision(size_type prec) { m_float_reserve = prec, m_float_ratio = uint64_t(pow(10, prec)), m_temp_buf_dot = m_temp_buf + prec; }
OutputHelper &flush() { return _write(), fflush(m_file_ptr), *this; }
void putchar(const char &c) {
if (m_cursor == m_end) _write();
*m_cursor++ = c;
}
template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
OutputHelper &operator<<(Tp ret) {
_reserve<MAX_INTEGER_SIZE>();
size_type len = 0;
if (ret >= 0)
do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;
while (ret);
else {
putchar('-');
do *(m_cursor + len++) = '0' - ret % 10, ret /= 10;
while (ret);
}
for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));
m_cursor += len;
return *this;
}
template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
OutputHelper &operator<<(Tp ret) {
_reserve<MAX_INTEGER_SIZE>();
size_type len = 0;
do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;
while (ret);
for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));
m_cursor += len;
return *this;
}
template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
OutputHelper &operator<<(Tp ret) {
if (ret < 0) {
putchar('-');
return *this << -ret;
}
ret *= m_float_ratio;
uint64_t integer = ret;
if (ret - integer >= 0.4999999999) integer++;
do {
*m_temp_buf_cursor++ = '0' + integer % 10;
integer /= 10;
} while (integer);
if (m_temp_buf_cursor > m_temp_buf_dot) {
do putchar(*--m_temp_buf_cursor);
while (m_temp_buf_cursor > m_temp_buf_dot);
putchar('.');
} else {
putchar('0'), putchar('.');
for (size_type i = m_temp_buf_dot - m_temp_buf_cursor; i--;) putchar('0');
}
do putchar(*--m_temp_buf_cursor);
while (m_temp_buf_cursor > m_temp_buf);
return *this;
}
OutputHelper &operator<<(const char &ret) {
putchar(ret);
return *this;
}
OutputHelper &operator<<(const char *ret) {
while (*ret) putchar(*ret++);
return *this;
}
OutputHelper &operator<<(const std::string &ret) { return *this << ret.data(); }
};
InputHelper &getline(InputHelper &ih, std::string &line) {
line.clear();
if (ih.getchar_checked() == EOF) return ih.set_bad();
while (!InputHelper::is_endline(ih.getchar_checked())) line += ih.getchar_unchecked(), ih.next();
if (ih.getchar_unchecked() != EOF) ih.next();
return ih;
}
}
}
using OY::IO::getline;
#endif
#ifndef __OY_SIFTHEAP__
#define __OY_SIFTHEAP__
namespace OY {
namespace Sift {
using size_type = uint32_t;
template <typename Sequence>
struct Getter;
template <typename Tp>
struct Getter<std::vector<Tp>> {
std::vector<Tp> &m_sequence;
Getter(std::vector<Tp> &sequence) : m_sequence(sequence) {}
const Tp &operator()(size_type index) const { return m_sequence[index]; }
};
template <typename Tp>
struct Getter<Tp *> {
Tp *m_sequence;
Getter(Tp *sequence) : m_sequence(sequence) {}
const Tp &operator()(size_type index) const { return *(m_sequence + index); }
};
template <typename Mapping, typename Compare = std::less<void>, size_type MAX_NODE = 1 << 20>
struct Heap {
static size_type s_buffer[MAX_NODE << 1], s_use_count;
size_type *m_heap, *m_pos, m_size;
Mapping m_map;
Compare m_comp;
Heap(size_type length, Mapping map, Compare comp = Compare()) : m_map(map), m_comp(comp) { resize(length); }
void resize(size_type length) {
m_heap = s_buffer + s_use_count, m_pos = s_buffer + s_use_count + length, m_size = 0, s_use_count += length << 1;
std::fill_n(m_pos, length, -1);
}
void sift_up(size_type i) {
size_type curpos = m_pos[i], p;
auto &&curvalue = m_map(i);
for (; curpos; curpos = (curpos - 1) >> 1) {
if (!m_comp(m_map(p = m_heap[(curpos - 1) >> 1]), curvalue)) break;
m_heap[m_pos[p] = curpos] = p;
}
m_heap[m_pos[i] = curpos] = i;
}
void sift_down(size_type i) {
size_type curpos = m_pos[i], c;
auto &&curvalue = m_map(i);
for (; (c = curpos * 2 + 1) < m_size; curpos = c) {
if (c + 1 < m_size && m_comp(m_map(m_heap[c]), m_map(m_heap[c + 1]))) c++;
if (!m_comp(curvalue, m_map(m_heap[c]))) break;
m_pos[m_heap[curpos] = m_heap[c]] = curpos;
}
m_heap[m_pos[i] = curpos] = i;
}
void clear() {
for (size_type i = 0; i != m_size; i++) m_pos[i] = -1;
m_size = 0;
}
void push(size_type i) {
if (!~m_pos[i]) {
m_pos[i] = m_size;
m_heap[m_size++] = i;
}
sift_up(i);
}
size_type top() const { return m_heap[0]; }
void pop() {
m_pos[m_heap[0]] = -1;
if (--m_size) {
m_pos[m_heap[m_size]] = 0;
m_heap[0] = m_heap[m_size];
sift_down(m_heap[0]);
}
}
bool empty() const { return !m_size; }
size_type size() const { return m_size; }
};
template <typename Mapping, typename Compare, size_type MAX_NODE>
size_type Heap<Mapping, Compare, MAX_NODE>::s_buffer[MAX_NODE << 1];
template <typename Mapping, typename Compare, size_type MAX_NODE>
size_type Heap<Mapping, Compare, MAX_NODE>::s_use_count;
}
template <typename Tp, typename Compare = std::less<Tp>, Sift::size_type MAX_NODE = 1 << 20, typename HeapType = Sift::Heap<Sift::Getter<std::vector<Tp>>, Compare, MAX_NODE>>
auto make_SiftHeap(Sift::size_type length, std::vector<Tp> &items, Compare comp = Compare()) -> HeapType { return HeapType(length, Sift::Getter<std::vector<Tp>>(items), comp); }
template <typename Tp, typename Compare = std::less<Tp>, Sift::size_type MAX_NODE = 1 << 20, typename HeapType = Sift::Heap<Sift::Getter<Tp *>, Compare, MAX_NODE>>
auto make_SiftHeap(Sift::size_type length, Tp *items, Compare comp = Compare()) -> HeapType { return HeapType(length, Sift::Getter<Tp *>(items), comp); }
template <typename Sequence>
using SiftGetter = Sift::Getter<Sequence>;
template <typename Mapping, typename Compare = std::less<void>, Sift::size_type MAX_NODE = 1 << 20>
using SiftHeap = Sift::Heap<Mapping, Compare, MAX_NODE>;
}
#endif
struct dsu {
dsu(int n) {
p.resize(n, -1);
pp.resize(n); for (int i = 0; i < n; i++) pp[i] = i;
r.resize(n, 0);
}
inline int par(int x) {
return pp[_par(x)];
}
inline int _par(int x) {
return p[x] == -1 ? x : p[x] = _par(p[x]);
}
inline void merge(int a, int b) {
a = _par(a); b = _par(b);
if (a == b)return;
if (r[a] < r[b]) {
swap(a, b);
swap(pp[a], pp[b]);
}
if (r[a] == r[b]) r[a]++;
p[b] = a;
}
vector<int> p, r, pp;
};
signed main() {
// ios_base::sync_with_stdio(false); cin.tie(NULL);
int N, D, T; cin >> N >> D >> T;
vector<int> t(N); for (auto& x : t) cin >> x;
int l = 0, r = 2e6, m = 0;
int ans = 0;
while (l < r) {//aliens HAHAHAhaha ha ha :sob:
m = (l + r) / 2;
vector<pair<int,int>> st; st.reserve(N);
struct node {
int p = -1;//prev
int n = -1;//next
int lz = 0;
int v = 0;
int c = 0; // count owo!!!
node() {};
node(int v, int c) : v(v), c(c) {};
};
vector<node> st2; st2.reserve(N);
dsu pls(N);
int start = 0;
int amt = 0;//amount added
function<void(int)> kill = [&](int i) {
int n = st2[i].n;
//assert(n != -1);
if (n == -1) return;
if ((st2[i].v + (int)st2[i].lz > st2[n].v)) {
int p = st2[i].p;
st2[n].p = p;
if (p != -1) {
st2[p].lz += st2[i].lz;
st2[p].n = n;
pls.merge(p, i); //merge i to p
kill(p);
}
else {
// DEAD
amt -= st2[i].lz; //recycle owo
start = n;
}
}
};
for (int i = 0; i < N; i++) {
//create and then upd
if (st2.size()) {
st2.push_back(node(st2[start].v + (int)amt + m, st2[start].c+1));
st2[i - 1].n = i; st2[i].p = i - 1;
kill(i - 1);
}
else {
st2.push_back(node());
}
int o = i;
if (t[i] <= T) {
while (st.size() && st.back().ff >= t[i] - i) {
st.pop_back();
}
st.push_back({ t[i] - i, i});
}
else {
while (st.size() && st.back().ff > T - i) st.pop_back();
if (st.size()) {
o = st.back().ss;
}
else o = -1;
}
//cout << o << ",";
if(o >= start){
int t = pls.par(o);
st2[t].lz++; amt++;
kill(t);
}
//cout << amt << ",";
}
//cout << endl;
int c = st2[start].c;
//cout << c << endl;
if (c <= D) {
r = m;
ans = round((int)st2[start].v + (int)amt - (int)D * m);
}
else {
//cout << "fuck" << endl;
l = m + 1;
}
}
cout << ans << endl;
// n log n inverse ackermann n please pass i swear to god
}
Compilation message (stderr)
prison.cpp: In constructor 'OY::IO::InputHelper::InputHelper(const char*)':
prison.cpp:44:18: warning: 'OY::IO::InputHelper::m_ok' will be initialized after [-Wreorder]
44 | bool m_ok;
| ^~~~
prison.cpp:43:53: warning: 'char* OY::IO::InputHelper::m_cursor' [-Wreorder]
43 | char m_buf[INPUT_BUFFER_SIZE], *m_end, *m_cursor;
| ^~~~~~~~
prison.cpp:63:22: warning: when initialized here [-Wreorder]
63 | explicit InputHelper(const char *inputFileName) : m_ok(true), m_cursor(m_buf + INPUT_BUFFER_SIZE), m_end(m_buf + INPUT_BUFFER_SIZE) { m_file_ptr = *inputFileName ? fopen(inputFileName, "rt") : stdin; }
| ^~~~~~~~~~~
prison.cpp:43:53: warning: 'OY::IO::InputHelper::m_cursor' will be initialized after [-Wreorder]
43 | char m_buf[INPUT_BUFFER_SIZE], *m_end, *m_cursor;
| ^~~~~~~~
prison.cpp:43:45: warning: 'char* OY::IO::InputHelper::m_end' [-Wreorder]
43 | char m_buf[INPUT_BUFFER_SIZE], *m_end, *m_cursor;
| ^~~~~
prison.cpp:63:22: warning: when initialized here [-Wreorder]
63 | explicit InputHelper(const char *inputFileName) : m_ok(true), m_cursor(m_buf + INPUT_BUFFER_SIZE), m_end(m_buf + INPUT_BUFFER_SIZE) { m_file_ptr = *inputFileName ? fopen(inputFileName, "rt") : stdin; }
| ^~~~~~~~~~~
prison.cpp: In constructor 'OY::IO::OutputHelper::OutputHelper(const char*, OY::IO::size_type)':
prison.cpp:138:54: warning: 'OY::IO::OutputHelper::m_cursor' will be initialized after [-Wreorder]
138 | char m_buf[OUTPUT_BUFFER_SIZE], *m_end, *m_cursor;
| ^~~~~~~~
prison.cpp:138:46: warning: 'char* OY::IO::OutputHelper::m_end' [-Wreorder]
138 | char m_buf[OUTPUT_BUFFER_SIZE], *m_end, *m_cursor;
| ^~~~~
prison.cpp:148:13: warning: when initialized here [-Wreorder]
148 | OutputHelper(const char *outputFileName, size_type prec = 6) : m_cursor(m_buf), m_end(m_buf + OUTPUT_BUFFER_SIZE), m_temp_buf_cursor(m_temp_buf) { m_file_ptr = *outputFileName ? fopen(outputFileName, "wt") : stdout, precision(prec); }
| ^~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
