| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 310943 |
2020-10-08T18:10:48 Z |
Falcon |
Hacker (BOI15_hac) |
C++17 |
|
565 ms |
36112 KB |
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N) for(int i = 0; i < (N); ++i)
#define rep1(i, N) for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e) for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back
#ifdef DEBUG
#define debug(x...) { dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals); }
#define light_debug(x) { dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << " " << #x << " = " << x << endl; dbg::light = 0; }
#else
#define debug(x...) 42
#define light_debug(x) 42
#endif
template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
constexpr ll INF{1LL << 50};
class lazy_segtree {
int N;
vector<ll> a, lzy;
void push(int n, int s, int e) {
ckmin(a[n], lzy[n]);
if(s != e)
ckmin(lzy[n << 1], lzy[n]), ckmin(lzy[n << 1 | 1], lzy[n]);
lzy[n] = INF;
}
void update(int n, int s, int e, int l, int r, ll v) {
push(n, s, e);
if(r < s || e < l) return;
if(l <= s && e <= r) {
ckmin(lzy[n], v);
push(n, s, e);
return;
}
int m = (s + e) >> 1;
update(n << 1, s, m, l, r, v); update(n << 1 | 1, m + 1, e, l, r, v);
a[n] = max(a[n << 1], a[n << 1 | 1]);
}
public:
lazy_segtree(int _N) : N{_N}, a(N << 2, INF), lzy(N << 2, INF) {}
void update(int l, int r, ll v) { update(1, 0, N - 1, l, r, v); }
ll query() { return a[1]; }
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
#ifdef DEBUG
freopen("debug", "w", stderr);
#endif
int n; cin >> n;
vi a(n); rep(i, n) cin >> a[i];
lazy_segtree seg(n);
int l{(n + 1) >> 1}, s{a[n - 1]};
rep(i, l - 1) s += a[i];
rep(i, n) {
int j{(i + l - 1) % n};
s += a[j] - a[(i + n - 1) % n];
if(j >= i) seg.update(i, j, s);
else seg.update(i, n - 1, s), seg.update(0, j, s);
}
cout << seg.query() << '\n';
#ifdef DEBUG
dbg::dout << "\nExecution time: " << clock() << "ms\n";
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
360 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
288 KB |
Output is correct |
| 12 |
Correct |
1 ms |
360 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
360 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
288 KB |
Output is correct |
| 12 |
Correct |
1 ms |
360 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
416 KB |
Output is correct |
| 22 |
Correct |
3 ms |
512 KB |
Output is correct |
| 23 |
Correct |
4 ms |
640 KB |
Output is correct |
| 24 |
Correct |
3 ms |
512 KB |
Output is correct |
| 25 |
Correct |
4 ms |
768 KB |
Output is correct |
| 26 |
Correct |
4 ms |
768 KB |
Output is correct |
| 27 |
Correct |
1 ms |
360 KB |
Output is correct |
| 28 |
Correct |
1 ms |
384 KB |
Output is correct |
| 29 |
Correct |
1 ms |
384 KB |
Output is correct |
| 30 |
Correct |
4 ms |
640 KB |
Output is correct |
| 31 |
Correct |
4 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
640 KB |
Output is correct |
| 4 |
Correct |
75 ms |
6064 KB |
Output is correct |
| 5 |
Correct |
203 ms |
14584 KB |
Output is correct |
| 6 |
Correct |
266 ms |
18168 KB |
Output is correct |
| 7 |
Correct |
317 ms |
21624 KB |
Output is correct |
| 8 |
Correct |
550 ms |
35832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
360 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
288 KB |
Output is correct |
| 12 |
Correct |
1 ms |
360 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
416 KB |
Output is correct |
| 22 |
Correct |
3 ms |
512 KB |
Output is correct |
| 23 |
Correct |
4 ms |
640 KB |
Output is correct |
| 24 |
Correct |
3 ms |
512 KB |
Output is correct |
| 25 |
Correct |
4 ms |
768 KB |
Output is correct |
| 26 |
Correct |
4 ms |
768 KB |
Output is correct |
| 27 |
Correct |
1 ms |
360 KB |
Output is correct |
| 28 |
Correct |
1 ms |
384 KB |
Output is correct |
| 29 |
Correct |
1 ms |
384 KB |
Output is correct |
| 30 |
Correct |
4 ms |
640 KB |
Output is correct |
| 31 |
Correct |
4 ms |
640 KB |
Output is correct |
| 32 |
Correct |
0 ms |
384 KB |
Output is correct |
| 33 |
Correct |
1 ms |
384 KB |
Output is correct |
| 34 |
Correct |
4 ms |
640 KB |
Output is correct |
| 35 |
Correct |
75 ms |
6064 KB |
Output is correct |
| 36 |
Correct |
203 ms |
14584 KB |
Output is correct |
| 37 |
Correct |
266 ms |
18168 KB |
Output is correct |
| 38 |
Correct |
317 ms |
21624 KB |
Output is correct |
| 39 |
Correct |
550 ms |
35832 KB |
Output is correct |
| 40 |
Correct |
8 ms |
1280 KB |
Output is correct |
| 41 |
Correct |
17 ms |
1792 KB |
Output is correct |
| 42 |
Correct |
27 ms |
2560 KB |
Output is correct |
| 43 |
Correct |
208 ms |
14584 KB |
Output is correct |
| 44 |
Correct |
565 ms |
35960 KB |
Output is correct |
| 45 |
Correct |
97 ms |
7400 KB |
Output is correct |
| 46 |
Correct |
324 ms |
21752 KB |
Output is correct |
| 47 |
Correct |
548 ms |
35832 KB |
Output is correct |
| 48 |
Correct |
560 ms |
36112 KB |
Output is correct |
| 49 |
Correct |
549 ms |
35320 KB |
Output is correct |
| 50 |
Correct |
563 ms |
35248 KB |
Output is correct |
