# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1179747 | Szymon_Pilipczuk | Growing Vegetables is Fun 4 (JOI21_ho_t1) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
int n;
using namespace std;
ll tr[400000];
#define ll long long
void add(int l,int r,ll v)
{
l+=n;
r+=n;
tr[l]+=v;
if(l!=r)tr[r]+=v;
while(l/2 != r/2)
{
if(l%2 == 0)tr[l+1]+=v;
if(r%2 == 1)tr[r-1]+=v;
l/=2;r/=2;
}
}
ll check(int p)
{
p+=n;
int ans = 0;
while(p > 0)
{
ans+=tr[p];
p/=2;
}
return ans;
}
int main()
{
cin>>n;
int a[n];
for(int i =0 ;i<n;i++)
{
cin>>a[i];
tr[i+n] = a[i];
}
ll ans = 0;
int i = 1;
int j = n-2;
while(i <=j)
{
if(check(i-1) < check(i))
{
i++;
continue;
}
if(check(j+1) < check(j))
{
j--;
continue;
}
ans += min(check(j+1)-check(j)+1,check(i-1)-check(i)+1);
add(i,j,min(check(j+1)-check(j)+1,check(i-1)-check(i)+1));
}
if(check(i) == check(j))
{
ans++;
}
cout<<ans;
}