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 endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, q;
ll a[maxn], pref[maxn];
void input()
{
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i];
cin >> q;
a[0] = 1e9 + 10;
a[n + 1] = 1e9 + 10;
}
vector < pair < int, int > > ranges;
void get_ranges()
{
for (int i = 1; i <= n; i ++)
pref[i] = pref[i - 1] + a[i];
pref[n + 1] = pref[n];
ranges.clear();
stack < int > st;
st.push(0);
for (int i = 1; i <= n; i ++)
{
while(!st.empty() && a[st.top()] < a[i])
st.pop();
if (pref[i - 1] - pref[st.top()] < a[i])
ranges.push_back({st.top() + 1, i - 1});
st.push(i);
}
while(!st.empty())
st.pop();
st.push(n + 1);
for (int i = n; i > 0; i --)
{
while(!st.empty() && a[st.top()] < a[i])
st.pop();
if (pref[st.top() - 1] - pref[i] < a[i])
ranges.push_back({i + 1, st.top() - 1});
st.push(i);
}
}
int b[maxn];
void solve_query(int left, int right)
{
get_ranges();
for (int i = 1; i <= n; i ++)
b[i] = 0;
for (pair < int, int > cur : ranges)
for (int i = cur.first; i <= cur.second; i ++)
b[i] ++;
//for (pair < int, int > cur : ranges)
// cout << cur.first << " : " << cur.second << endl;
int lb = left, rb = right;
for (int i = left; i <= right; i ++)
{
if (a[i] > pref[i - 1] - pref[left - 1])
lb = max(lb, i);
if (a[i] > pref[right] - pref[i])
rb = min(rb, i);
}
int minx = 1e9;
for (int i = lb; i <= rb; i ++)
minx = min(minx, b[i]);
int ans = 0;
for (int i = lb; i <= rb; i ++)
if (b[i] == minx)
ans ++;
cout << ans << endl;
}
void simulate()
{
for (int i = 1; i <= q; i ++)
{
int type;
cin >> type;
if (type == 1)
{
int idx;
ll x;
cin >> idx >> x;
a[idx] = x;
}
else
{
int l, r;
cin >> l >> r;
solve_query(l, r);
}
}
}
void solve()
{
input();
simulate();
}
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int main()
{
speed();
solve();
return 0;
}
# | 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... |