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>
#define int long long
// using ll = long long;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
using pii = pair<int, int>;
vector<int> ll, rr, v, p, ok;
void dfs(int x, int l, int r)
{
ok[x] = 1;
if (ll[x] != -1 && v[x] <= p[x - 1] - p[l - 1])
dfs(ll[x], l, x - 1);
if (rr[x] != -1 && v[x] <= p[r] - p[x])
dfs(rr[x], x + 1, r);
}
void solve()
{
int n;
cin >> n;
v.assign(n + 1, 0);
for (int i = 1; i <= n; ++i)
cin >> v[i];
auto v0 = v;
int n0 = n;
int q;
cin >> q;
while (q--)
{
int t, a, b;
cin >> t >> a >> b;
if (t == 1)
{
v0[a] = b;
continue;
}
v.assign(1, 0);
for (int i = a; i <= b; ++i)
v.emplace_back(v0[i]);
n = sz(v) - 1;
p = v;
for (int i = 1; i <= n; ++i)
p[i] += p[i - 1];
v[0] = INT_MAX, v.emplace_back(INT_MAX);
--v[0];
vector<int> l(n + 2, -1), r(n + 2, -1);
vector<int> stk;
stk.emplace_back(0);
for (int i = 1; i <= n; ++i)
{
while (v[stk.back()] < v[i])
stk.pop_back();
l[i] = stk.back();
stk.emplace_back(i);
}
stk.clear();
stk.emplace_back(n + 1);
for (int i = n; i >= 1; --i)
{
while (v[stk.back()] <= v[i])
stk.pop_back();
r[i] = stk.back();
stk.emplace_back(i);
}
ll.assign(n + 2, -1), rr = ll;
for (int i = 1; i <= n; ++i)
{
if (v[l[i]] < v[r[i]])
{
assert(rr[l[i]] == -1);
rr[l[i]] = i;
}
else
{
assert(ll[r[i]] == -1);
ll[r[i]] = i;
}
}
ok.assign(n + 1, 0);
dfs(rr[0], 1, n);
cout << accumulate(all(ok), 0) << '\n';
}
}
/*
*/
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Compilation message (stderr)
fish2.cpp: In function 'void solve()':
fish2.cpp:28:9: warning: unused variable 'n0' [-Wunused-variable]
28 | int n0 = 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... |