#pragma GCC optimize("O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx")
// #pragma GCC diagnostic ignored "-W"
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#include <utility>
#include <functional>
#include <complex>
#include <climits>
#include <random>
#include <thread>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#endif
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/rope>
using namespace std;
// using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define pii pair<int, int>
#define vint vector<int>
#define vpii vector<pair<int, int>>
#define SS stringstream
#define PQ priority_queue
#define MS(x, v) memset((x), (v), sizeof(x))
#define RZUNI(x) sort(x.begin(), x.end()), x.resize(unique(x.begin(), x.end()) - x.begin())
#define FLH fflush(stdout)
#define CPPinput ios_base::sync_with_stdio(0), cin.tie(0)
#define FIO(fname) freopen(fname ".in", "r", stdin), freopen(fname ".out", "w", stdout)
#define FIN(fname) freopen(fname, "r", stdin)
#define FOUT(fname) freopen(fname, "w", stdout)
#define tm Ovuvuevuevue
#define y1 Enyetuenwuevue
#define left Ugbemugbem
#define ws Osas
#define dec tetteterette
#define expl explexplexpl
#define data datadetedoto
#ifdef WEAK
#include"/home/edison/Coding/cpp/template/debug.cpp"
#define DEB(...) printf(__VA_ARGS__), fflush(stdout)
#define WHR() printf("%s: Line %d", __PRETTY_FUNCTION__, __LINE__), fflush(stdout)
#define LOG(...) printf("%s: Line %d ", __PRETTY_FUNCTION__, __LINE__), printf(__VA_ARGS__), fflush(stdout)
#define DEBUG 1
#define exit(x) cout << "exit code " << x << endl, exit(0)
#else
#define PDE(...) ;
#define DEB(...) ;
#define WHR() ;
#define LOG(...) ;
#define DEBUG 0
#endif
#define lowbit(x) ((x) & (-(x)))
const long double PI = 3.14159265358979323846264338327950288;
const long double eps = 1e-10;
const long long mod = 1e9+7;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#define fread fread_unlocked
#define fwrite fwrite_unlocked
inline char gtx() {
const int N=4096;
static char buffer[N];
static char *p = buffer, *end = buffer;
if (p == end) {
if ((end = buffer + fread(buffer, 1, N, stdin)) == buffer) return EOF;
p = buffer;
} return *p++;
}
template <typename T>
inline void rit(T &x) {
char c; bool fg = 0;
while (c = gtx(), (c < '0' && c != '-') || c > '9');
c == '-' ? (fg = 1, x = 0) : (x = c & 15);
while (c = gtx(), c >= '0' && c <= '9') x = x * 10 + (c & 15);
if (fg) x = -x;
}
template <typename T, typename ...Args>
inline void rit(T& x, Args& ...args) { rit(x), rit(args...); }
template <typename T>
inline void ruit(T &x) {
char c;
while (c = gtx(), c < '0' || c > '9');
x = c & 15;
while (c = gtx(), c >= '0' && c <= '9') x = x * 10 + (c & 15);
}
template <typename T, typename ...Args>
inline void ruit(T& x, Args& ...args) { ruit(x), ruit(args...); }
template <typename T>
inline bool rit_save(T &x) {
char c; bool fg = 0;
while (c = gtx(), (c < '0' && c != '-') || c > '9') if (c == EOF) return false;
c == '-' ? (fg = 1, x = 0) : (x = c & 15);
while (c = gtx(), c >= '0' && c <= '9') x = x * 10 + (c & 15);
if (fg) x = -x; return true;
}
template <typename T, typename ...Args>
inline bool rit_save(T& x, Args& ...args) { return rit_save(x) && rit_save(args...); }
template <typename T>
inline bool ruit_save(T &x) {
char c;
while (c = gtx(), c < '0' || c > '9') if (c == EOF) return false;
x = c & 15;
while (c = gtx(), c >= '0' && c <= '9') x = x * 10 + (c & 15);
return true;
}
template <typename T, typename ...Args>
inline bool ruit_save(T& x, Args& ...args) { return ruit_save(x) && ruit_save(args...); }
struct outputter {
char buffer[4112], *ptr = buffer, *end = buffer + 4096;
inline void writebyte(char c) {
*ptr = c; ++ptr;
if (ptr > end) fwrite(buffer, sizeof(char), ptr-buffer, stdout), ptr = buffer;
}
template <typename T> inline void writeint(T x, char endc = '\n') {
if (!x) { *ptr = '0', ++ptr; }
else {
char *s = ptr, c; T t;
while (x) { t = x / 10; c = x - 10 * t + '0'; *ptr = c, ++ptr, x = t; }
char *f = ptr - 1; while (s < f) swap(*s, *f), ++s, --f;
}
*ptr = endc, ++ptr;
if (ptr > end) fwrite(buffer, sizeof(char), ptr - buffer, stdout), ptr = buffer;
}
template <typename T>
inline void output(T x) { writeint(x, '\n'); }
template <typename T,typename ...Args>
inline void output(T x,Args ...args) { writeint(x, ' '); output(args...); }
template <typename ...Args> inline void operator()(Args ...args) { output(args...); }
outputter() {}
~outputter() { fwrite(buffer, sizeof(char), ptr - buffer, stdout); }
} pit;
#pragma GCC diagnostic pop
void cdp(vector<int> &v, int l, int r, int tl, int tr, vector<double> &ans) {
int m = (l + r) >> 1;
if (r < l) return;
int t = -1;
double mx = -1;
for (int i = tl; i <= min(tr, m); ++i) {
double z = sqrt(m - i) + v[i];
if (z > mx) mx = z, t = i;
}
ans[m] = mx;
cdp(v, l, m - 1, tl, t, ans);
cdp(v, m + 1, r, t, tr, ans);
}
int main() {
int n; ruit(n);
vector<int> v(n);
for (int i = 0; i < n; ++i) ruit(v[i]);
vector<double> ans1(n), ans2(n);
cdp(v, 0, n - 1, 0, n - 1, ans1);
reverse(v.begin(), v.end());
cdp(v, 0, n - 1, 0, n - 1, ans2);
reverse(v.begin(), v.end());
reverse(ans2.begin(), ans2.end());
for (int i = 0; i < n; ++i) pit((int)ceil(max(ans1[i], ans2[i])) - v[i]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
2560 KB |
Output is correct |
| 2 |
Correct |
10 ms |
2048 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
3712 KB |
Output is correct |
| 2 |
Correct |
19 ms |
3576 KB |
Output is correct |
| 3 |
Correct |
24 ms |
3840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
8184 KB |
Output is correct |
| 2 |
Correct |
43 ms |
7672 KB |
Output is correct |
| 3 |
Correct |
47 ms |
7672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
14072 KB |
Output is correct |
| 2 |
Correct |
69 ms |
12152 KB |
Output is correct |
| 3 |
Correct |
77 ms |
12792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
19960 KB |
Output is correct |
| 2 |
Correct |
99 ms |
17016 KB |
Output is correct |
| 3 |
Correct |
106 ms |
18040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
17528 KB |
Output is correct |
| 2 |
Correct |
97 ms |
17016 KB |
Output is correct |
| 3 |
Correct |
112 ms |
18040 KB |
Output is correct |
