#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set=tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
constexpr int N = 500000;
constexpr int T = 710;
__attribute__((always_inline)) void smax(int& x, int y) {x = x < y ? y : x;}
int a[N];
int pf[N], sf[N];
int pos[T][2];
int32_t main() {
fastio;
int n; cin >> n;
rep(i, n) cin >> a[i];
int m = *max_element(a, a + n);
memset(pos, -1, sizeof(pos));
rep(i, n) if(m - a[i] < T) {
int s = m - a[i];
if(!~pos[s][0]) pos[s][0] = i;
else pos[s][1] = i;
}
rep(_i, T) rep(_j, 2) if(~pos[_i][_j]) {
int i = pos[_i][_j];
for(int j = 0; i + j * j + 1 < n; j++) smax(pf[i + j * j + 1], a[i] + j + 1);
for(int j = 0; i - j * j > 0; j++) smax(sf[i - j * j - 1], a[i] + j + 1);
}
for(int i = 1; i < n; i++) smax(pf[i], pf[i - 1]);
for(int i = n - 2; ~i; i--) smax(sf[i], sf[i + 1]);
rep(i, n) cout << max({pf[i], sf[i], a[i]}) - a[i] << endl;
}
Compilation message
pio.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization("unroll-loops, no-stack-protector")
|
pio.cpp:48:37: warning: always_inline function might not be inlinable [-Wattributes]
48 | __attribute__((always_inline)) void smax(int& x, int y) {x = x < y ? y : x;}
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
1996 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1484 KB |
Output is correct |
| 3 |
Correct |
15 ms |
1956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
2788 KB |
Output is correct |
| 2 |
Correct |
23 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
24 ms |
3012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
6340 KB |
Output is correct |
| 2 |
Correct |
52 ms |
5816 KB |
Output is correct |
| 3 |
Correct |
57 ms |
5956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
11260 KB |
Output is correct |
| 2 |
Correct |
83 ms |
9312 KB |
Output is correct |
| 3 |
Correct |
81 ms |
9956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
15964 KB |
Output is correct |
| 2 |
Correct |
134 ms |
12996 KB |
Output is correct |
| 3 |
Correct |
114 ms |
14052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
13492 KB |
Output is correct |
| 2 |
Correct |
122 ms |
12996 KB |
Output is correct |
| 3 |
Correct |
114 ms |
14024 KB |
Output is correct |
