| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 600973 |
2022-07-21T09:40:12 Z |
KoD |
Fish 2 (JOI22_fish2) |
C++17 |
|
4000 ms |
16324 KB |
#include <bits/stdc++.h>
using ll = long long;
using std::pair;
using std::vector;
class Sequence {
struct Data {
int max;
ll sum;
static Data identity() {
return {0, 0};
}
static Data make(const int x) {
return {x, x};
}
friend Data operator+(const Data& l, const Data& r) {
return {std::max(l.max, r.max), l.sum + r.sum};
}
};
int size, logn;
vector<Data> data;
public:
explicit Sequence(const vector<int>& vec) {
logn = 0;
while ((1 << logn) < (int)vec.size()) {
logn += 1;
}
size = 1 << logn;
data.resize(2 * size, Data::identity());
for (int i = 0; i < (int)vec.size(); ++i) {
data[size + i] = Data::make(vec[i]);
}
for (int i = size - 1; i > 0; --i) {
data[i] = data[2 * i] + data[2 * i + 1];
}
}
void update(int i, const int x) {
i += size;
data[i] = Data::make(x);
while (i > 1) {
i >>= 1;
data[i] = data[2 * i] + data[2 * i + 1];
}
}
ll sum(int l, int r) const {
l += size;
r += size;
ll ret = 0;
while (l < r) {
if (l & 1) {
ret += data[l].sum;
l += 1;
}
if (r & 1) {
r -= 1;
ret += data[r].sum;
}
l >>= 1;
r >>= 1;
}
return ret;
}
int upb_to_right(int l, const ll x) {
if (l == size) return -1;
l += size;
do {
while (!(l & 1)) l >>= 1;
if (data[l].max > x) {
while (l < size) {
l <<= 1;
if (data[l].max <= x) {
l += 1;
}
}
return l - size;
}
l >>= 1;
l += 1;
} while (l & (l - 1));
return -1;
}
int upb_to_left(int r, const ll x) {
if (r == 0) return -1;
r += size;
do {
while (!(r & 1)) r >>= 1;
r -= 1;
if (data[r].max > x) {
while (r < size) {
r <<= 1;
if (data[r + 1].max > x) {
r += 1;
}
}
return r - size;
}
r >>= 1;
} while (r & (r - 1));
return -1;
}
};
class Intervals {
int size, logn;
vector<vector<pair<int, int>>> data;
public:
explicit Intervals(const int n) {
logn = 0;
while ((1 << logn) < n) {
logn += 1;
}
size = 1 << logn;
data.resize(2 * size);
}
void add_rec(int u, int l, int r, int a, int b) {
const int m = (a + b) / 2;
if (l <= m and m < r) {
data[u].emplace_back(l, r);
return;
}
if (r <= m) {
add_rec(2 * u, l, r, a, m);
} else {
add_rec(2 * u + 1, l, r, m, b);
}
}
void add(const int l, const int r) {
add_rec(1, l, r, 0, size);
// int i = l + size, j = l + size + 1, k = 1;
// while (j < r) {
// if (!(i & 1)) {
// j += k;
// }
// i >>= 1;
// k <<= 1;
// }
// data[i].emplace_back(l, r);
}
template <class F>
void pop(const int k, const F& f) {
for (auto& vec : data) {
for (int i = 0; i < (int)vec.size(); ++i) {
const auto& [l, r] = vec[i];
if (l <= k and k < r) {
f(l, r);
std::swap(vec[i], vec.back());
vec.pop_back();
}
}
}
int i = k + size;
while (i > 0) {
while (!data[i].empty()) {
const auto& [l, r] = data[i].back();
if (l <= k and k < r) {
f(l, r);
data[i].pop_back();
} else {
break;
}
}
i >>= 1;
}
}
};
class SegmentTree {
struct Data {
int min, cnt;
static Data identity() {
return {1000000000, 0};
}
static Data make(const int x) {
return {x, 1};
}
friend Data operator+(const Data& l, const Data& r) {
const int m = std::min(l.min, r.min);
return {m, (l.min == m ? l.cnt : 0) + (r.min == m ? r.cnt : 0)};
}
};
int size, logn;
vector<Data> data;
vector<int> add;
void apply(const int k, const int a) {
data[k].min += a;
if (k < size) {
add[k] += a;
}
}
void flush(const int k) {
if (add[k] != 0) {
apply(2 * k, add[k]);
apply(2 * k + 1, add[k]);
add[k] = 0;
}
}
void push(const int k) {
const int lsb = __builtin_ctz(k);
for (int d = logn; d > lsb; --d) {
flush(k >> d);
}
}
void fetch(const int k) {
data[k] = data[2 * k] + data[2 * k + 1];
}
void pull(int k) {
k >>= __builtin_ctz(k);
while (k > 1) {
fetch(k >>= 1);
}
}
public:
explicit SegmentTree(const int n) {
logn = 0;
while ((1 << logn) < n) {
logn += 1;
}
size = 1 << logn;
data.resize(2 * size, Data::identity());
for (int i = 0; i < n; ++i) {
data[size + i] = Data::make(0);
}
for (int i = size - 1; i > 0; --i) {
data[i] = data[2 * i] + data[2 * i + 1];
}
add.resize(size);
}
void operate(int l, int r, const int x) {
l += size;
r += size;
push(l);
push(r);
const int lc = l, rc = r;
while (l < r) {
if (l & 1) {
apply(l, x);
l += 1;
}
if (r & 1) {
r -= 1;
apply(r, x);
}
l >>= 1;
r >>= 1;
}
pull(lc);
pull(rc);
}
int fold(int l, int r) {
l += size;
r += size;
push(l);
push(r);
Data ret = Data::identity();
while (l < r) {
if (l & 1) {
ret = ret + data[l];
l += 1;
}
if (r & 1) {
r -= 1;
ret = data[r] + ret;
}
l >>= 1;
r >>= 1;
}
return ret.cnt;
}
};
int main() {
int N;
std::cin >> N;
vector<int> A(N);
for (auto& x : A) {
std::cin >> x;
}
Sequence seq(A);
Intervals range(N);
SegmentTree seg(N);
const auto insert = [&](int l, int r) {
if (l + 1 < r) {
seg.operate(l + 1, r, 1);
range.add(l, r + 1);
}
};
const auto erase = [&](const int l, const int r) {
seg.operate(l + 1, r - 1, -1);
};
{
vector<ll> accum(N + 1);
for (int i = 0; i < N; ++i) {
accum[i + 1] = accum[i] + A[i];
}
vector<int> stack;
const auto test = [&](const int l, const int r) {
if (std::min(A[l], A[r]) > accum[r] - accum[l + 1]) {
insert(l, r);
}
};
for (int i = 0; i < N; ++i) {
while (!stack.empty() and A[stack.back()] < A[i]) {
test(stack.back(), i);
stack.pop_back();
}
if (!stack.empty()) {
test(stack.back(), i);
}
stack.push_back(i);
}
}
int Q;
std::cin >> Q;
while (Q--) {
int t;
std::cin >> t;
if (t == 1) {
int i, x;
std::cin >> i >> x;
i -= 1;
A[i] = x;
seq.update(i, x);
range.pop(i, erase);
vector<pair<int, int>> left, right;
{
int k = i + 1;
ll sum = 0;
while (k < N) {
right.emplace_back(k, seq.sum(i + 1, k));
sum += A[k];
k = seq.upb_to_right(k + 1, sum);
if (k == -1) {
break;
}
}
}
{
int k = i - 1;
ll sum = 0;
while (k >= 0) {
left.emplace_back(k, seq.sum(k + 1, i));
sum += A[k];
k = seq.upb_to_left(k, sum);
if (k == -1) {
break;
}
}
}
for (const auto& [l, sl] : left) {
if (std::min(A[i], A[l]) > sl) {
insert(l, i);
}
}
for (const auto& [r, sr] : right) {
if (std::min(A[i], A[r]) > sr) {
insert(i, r);
}
}
for (const auto& [l, sl] : left) {
for (const auto& [r, sr] : right) {
if (std::min(A[l], A[r]) > sl + A[i] + sr) {
insert(l, r);
}
}
}
} else {
int l, r;
std::cin >> l >> r;
l -= 1;
{
ll sum = 0;
const int lc = l;
int cand = l;
while (true) {
sum += A[l];
const int k = seq.upb_to_right(l + 1, sum);
if (k == -1 or k >= r) {
break;
}
if (seq.sum(lc, k) < A[k]) {
cand = k;
}
l = k;
}
l = cand;
}
{
ll sum = 0;
const int rc = r;
int cand = r;
while (true) {
sum += A[r - 1];
const int k = seq.upb_to_left(r - 1, sum);
if (k == -1 or k < l) {
break;
}
if (seq.sum(k + 1, rc) < A[k]) {
cand = k + 1;
}
r = k + 1;
}
r = cand;
}
std::cout << seg.fold(l, r) << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
66 ms |
15636 KB |
Output is correct |
| 3 |
Correct |
62 ms |
15616 KB |
Output is correct |
| 4 |
Correct |
59 ms |
15612 KB |
Output is correct |
| 5 |
Correct |
53 ms |
15636 KB |
Output is correct |
| 6 |
Correct |
75 ms |
15652 KB |
Output is correct |
| 7 |
Correct |
34 ms |
15064 KB |
Output is correct |
| 8 |
Correct |
57 ms |
15700 KB |
Output is correct |
| 9 |
Correct |
39 ms |
15108 KB |
Output is correct |
| 10 |
Correct |
48 ms |
15144 KB |
Output is correct |
| 11 |
Correct |
45 ms |
15140 KB |
Output is correct |
| 12 |
Correct |
44 ms |
15412 KB |
Output is correct |
| 13 |
Correct |
36 ms |
15404 KB |
Output is correct |
| 14 |
Correct |
57 ms |
16308 KB |
Output is correct |
| 15 |
Correct |
57 ms |
15792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
66 ms |
15636 KB |
Output is correct |
| 3 |
Correct |
62 ms |
15616 KB |
Output is correct |
| 4 |
Correct |
59 ms |
15612 KB |
Output is correct |
| 5 |
Correct |
53 ms |
15636 KB |
Output is correct |
| 6 |
Correct |
75 ms |
15652 KB |
Output is correct |
| 7 |
Correct |
34 ms |
15064 KB |
Output is correct |
| 8 |
Correct |
57 ms |
15700 KB |
Output is correct |
| 9 |
Correct |
39 ms |
15108 KB |
Output is correct |
| 10 |
Correct |
48 ms |
15144 KB |
Output is correct |
| 11 |
Correct |
45 ms |
15140 KB |
Output is correct |
| 12 |
Correct |
44 ms |
15412 KB |
Output is correct |
| 13 |
Correct |
36 ms |
15404 KB |
Output is correct |
| 14 |
Correct |
57 ms |
16308 KB |
Output is correct |
| 15 |
Correct |
57 ms |
15792 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
529 ms |
15652 KB |
Output is correct |
| 18 |
Correct |
399 ms |
15692 KB |
Output is correct |
| 19 |
Correct |
543 ms |
15692 KB |
Output is correct |
| 20 |
Correct |
540 ms |
15732 KB |
Output is correct |
| 21 |
Correct |
505 ms |
15768 KB |
Output is correct |
| 22 |
Correct |
377 ms |
15660 KB |
Output is correct |
| 23 |
Correct |
498 ms |
15636 KB |
Output is correct |
| 24 |
Correct |
563 ms |
15844 KB |
Output is correct |
| 25 |
Correct |
515 ms |
15736 KB |
Output is correct |
| 26 |
Correct |
601 ms |
15736 KB |
Output is correct |
| 27 |
Correct |
345 ms |
15672 KB |
Output is correct |
| 28 |
Correct |
389 ms |
15684 KB |
Output is correct |
| 29 |
Correct |
449 ms |
15596 KB |
Output is correct |
| 30 |
Correct |
648 ms |
15272 KB |
Output is correct |
| 31 |
Correct |
667 ms |
15172 KB |
Output is correct |
| 32 |
Correct |
805 ms |
15276 KB |
Output is correct |
| 33 |
Correct |
442 ms |
15188 KB |
Output is correct |
| 34 |
Correct |
695 ms |
15056 KB |
Output is correct |
| 35 |
Correct |
493 ms |
15028 KB |
Output is correct |
| 36 |
Correct |
419 ms |
15344 KB |
Output is correct |
| 37 |
Correct |
388 ms |
15304 KB |
Output is correct |
| 38 |
Correct |
321 ms |
15564 KB |
Output is correct |
| 39 |
Correct |
393 ms |
16324 KB |
Output is correct |
| 40 |
Correct |
328 ms |
15916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
66 ms |
15636 KB |
Output is correct |
| 3 |
Correct |
62 ms |
15616 KB |
Output is correct |
| 4 |
Correct |
59 ms |
15612 KB |
Output is correct |
| 5 |
Correct |
53 ms |
15636 KB |
Output is correct |
| 6 |
Correct |
75 ms |
15652 KB |
Output is correct |
| 7 |
Correct |
34 ms |
15064 KB |
Output is correct |
| 8 |
Correct |
57 ms |
15700 KB |
Output is correct |
| 9 |
Correct |
39 ms |
15108 KB |
Output is correct |
| 10 |
Correct |
48 ms |
15144 KB |
Output is correct |
| 11 |
Correct |
45 ms |
15140 KB |
Output is correct |
| 12 |
Correct |
44 ms |
15412 KB |
Output is correct |
| 13 |
Correct |
36 ms |
15404 KB |
Output is correct |
| 14 |
Correct |
57 ms |
16308 KB |
Output is correct |
| 15 |
Correct |
57 ms |
15792 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Execution timed out |
4064 ms |
15608 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
