Submission #395841

#	Time	Username	Problem	Language	Result	Execution time	Memory
395841		tduong0806	Lightning Conductor (POI11_pio)	C++14	100 / 100	134 ms	15964 KiB

pio

#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 (stderr)

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;}
      |                                     ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10