oj.uz

답안 #395841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395841 2021-04-29T03:29:21 Z tduong0806 Lightning Conductor (POI11_pio) C++14
100 / 100
 134 ms 15964 KB 
#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;}
      |                                     ^~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1276 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 1868 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 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

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 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

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 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

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 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

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 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

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 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