# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
853901 | 2023-09-25T12:46:20 Z | x0r | Lightning Conductor (POI11_pio) | C++17 | 356 ms | 65536 KB |
#include <bits/stdc++.h> #define name "" #define ll long long #define ld long double #define fi first #define se second #define pll pair < ll, ll > #define pii pair < int, int > #define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define SZE(x) ((int)(x).size()) #define pb push_back #define mp make_pair #define lnode node * 2, l, (l + r) / 2 #define rnode node * 2 + 1, (l + r) / 2 + 1, r using namespace std; const ld EPS = 1e-9; const int INF = 1e9 + 7; const ll LINF = 1E18; const int NMAX = 2e5; const ll MOD = 1e9 + 7; const ll BASE = 2309; const int LG = 19; ll n, a[NMAX + 3], st[NMAX + 3][LG + 3]; ll get(int l, int r) { int k = __lg(r - l + 1); return max(st[l][k], st[r - (1 << k) + 1][k]); } int main() { fast; if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } //int t; cin >> t; while (t --) sol(); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; st[i][0] = a[i]; } for (int j = 1; j <= LG; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); for (int i = 1; i <= n; i++) { ll res = 0; for (int j = 0; i - j * j > 1; j++) { int l = max(1, i - (j + 1) * (j + 1)), r = (i - j * j - 1); res = max(res, get(l, r) + (j + 1) - a[i]); } for (int j = 0; i + j * j < n; j++) { int l = i + j * j + 1, r = min((int)n, i + (j + 1) * (j + 1)); res = max(res, get(l, r) + (j + 1) - a[i]); } cout << res << '\n'; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 59 ms | 9304 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 106 ms | 13904 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 171 ms | 15780 KB | Output is correct |
2 | Correct | 168 ms | 15332 KB | Output is correct |
3 | Correct | 169 ms | 15632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 330 ms | 22608 KB | Output is correct |
2 | Correct | 356 ms | 22548 KB | Output is correct |
3 | Correct | 290 ms | 22596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 153 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 148 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 159 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 150 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |