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>
using namespace std;
#define ll long long
const int nx=1e5+5;
ll n, q, t, x, y, a[nx], l[nx], r[nx], sm[nx], rt, dp[nx], res;
void dfs(int u)
{
sm[u]=a[u];
if (l[u]) dfs(l[u]), sm[u]+=sm[l[u]];
if (r[u]) dfs(r[u]), sm[u]+=sm[r[u]];
}
void dfs2(int u)
{
if (l[u]&&sm[l[u]]>=a[u]) dp[l[u]]=1, dfs2(l[u]);
if (r[u]&&sm[r[u]]>=a[u]) dp[r[u]]=1, dfs2(r[u]);
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n;
for (int i=1; i<=n; i++) cin>>a[i];
cin>>q>>t>>x>>y;
stack<ll> s;
for (int i=1; i<=n; i++)
{
while (!s.empty()&&a[s.top()]<a[i]) l[i]=s.top(), s.pop();
if (s.empty()) rt=i;
else r[s.top()]=i;
s.push(i);
}
//cout<<"rt "<<rt<<'\n';
//for (int i=1; i<=n;i ++) cout<<i<<' '<<l[i]<<' '<<r[i]<<'\n';
dfs(rt);
dp[rt]=1;
dfs2(rt);
for (int i=1; i<=n; i++) res+=dp[i];
cout<<res;
}
# | 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... |