This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;
template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;
const int N = 1 << 17, INF = 0x3f3f3f3f;
pair<int, int> t[2 * N];
int mod[2 * N];
pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
if (a.x == b.x) {
return {a.x, a.y + b.y};
}
return min(a, b);
}
void tapply(int i, int x) {
t[i].x += x;
mod[i] += x;
}
void tpush(int i) {
if (mod[i]) {
tapply(2 * i + 1, mod[i]);
tapply(2 * i + 2, mod[i]);
mod[i] = 0;
}
}
void tpull(int i) {
t[i] = merge(t[2 * i + 1], t[2 * i + 2]);
}
void tadd(int ql, int qr, int x, int ci = 0, int cl = 0, int cr = N) {
if (ql <= cl && cr <= qr) {
tapply(ci, x);
return;
}
if (qr <= cl || cr <= ql) {
return;
}
int mid = (cl + cr) / 2;
tpush(ci);
tadd(ql, qr, x, 2 * ci + 1, cl, mid);
tadd(ql, qr, x, 2 * ci + 2, mid, cr);
tpull(ci);
}
pair<int, int> g[2 * N];
ll gs[2 * N];
void gset(int i, int x) {
i += N;
g[i] = {x, i};
gs[i] = x;
i /= 2;
while (i) {
g[i] = max(g[2 * i], g[2 * i + 1]);
gs[i] = gs[2 * i] + gs[2 * i + 1];
i /= 2;
}
}
pair<int, int> gget(int l, int r) {
l += N, r += N - 1;
pair<int, int> ans = {-1, -1};
while (l <= r) {
if (l & 1) ans = max(ans, g[l]);
if (!(r & 1)) ans = max(ans, g[r]);
l = (l + 1) / 2;
r = (r - 1) / 2;
}
return ans;
}
ll gsum(int l, int r) {
l += N, r += N - 1;
ll ans = 0;
while (l <= r) {
if (l & 1) ans += gs[l];
if (!(r & 1)) ans += gs[r];
l = (l + 1) / 2;
r = (r - 1) / 2;
}
return ans;
}
int gfirstgreater(int ql, int qr, ll x, int ci = 1, int cl = 0, int cr = N) {
if (qr <= cl || cr <= ql || g[ci].x <= x) {
return qr;
}
if (cr - cl == 1) {
return cl;
}
int mid = (cl + cr) / 2;
int res = gfirstgreater(ql, qr, x, 2 * ci, cl, mid);
if (res >= qr) {
return gfirstgreater(ql, qr, x, 2 * ci + 1, mid, cr);
} else {
return res;
}
}
int glastgreater(int ql, int qr, ll x, int ci = 1, int cl = 0, int cr = N) {
if (qr <= cl || cr <= ql || g[ci].x <= x) {
return ql - 1;
}
if (cr - cl == 1) {
return cl;
}
int mid = (cl + cr) / 2;
int res = glastgreater(ql, qr, x, 2 * ci + 1, mid, cr);
if (res < ql) {
return glastgreater(ql, qr, x, 2 * ci, cl, mid);
} else {
return res;
}
}
int a[N], n;
int up[N], left_[N], right_[N];
int ai(int i) {
if (i < 0 || i >= n) {
return +INF;
}
return a[i];
}
void set_up_to(int i, int x) {
if (up[i] != x) {
up[i] = x;
if (!x) {
tadd(left_[i] + 1, right_[i], -1);
} else {
tadd(left_[i] + 1, right_[i], 1);
}
}
}
pair<int, int> get_bounds(int i, ll s = -1) {
if (s == -1) {
s = a[i];
}
return {glastgreater(0, i, s), gfirstgreater(i, n, s)};
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
g[N + i] = {a[i], i};
gs[N + i] = a[i];
}
for (int i = 0; i < n; ++i) {
t[N - 1 + i] = {0, 1};
}
for (int i = N - 1; i--; ) {
t[i] = merge(t[2 * i + 1], t[2 * i + 2]);
mod[i] = 0;
}
for (int i = N; i--; ) {
g[i] = max(g[2 * i], g[2 * i + 1]);
gs[i] = gs[2 * i] + gs[2 * i + 1];
}
for (int i = 0; i < n; ++i) {
left_[i] = glastgreater(0, i, a[i]);
right_[i] = gfirstgreater(i + 1, n, a[i] - 1);
if (gsum(left_[i] + 1, right_[i]) < min(ai(left_[i]), ai(right_[i])) &&
(left_[i] != -1 || right_[i] != n)) {
set_up_to(i, 1);
}
}
cout << t[0].y << "\n";
// int queries;
// cin >> queries;
// while (queries--) {
// int type, l, r;
// cin >> type >> l >> r;
// if (type == 1) {
// // a[l - 1] = r;
// // gset(l - 1, r);
// assert(0);
// } else {
// cout << query(l - 1, r) << "\n";
// }
// }
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |