#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define INF 1023456789
#define LINF 1023456789123456789
#define lb(x,v) lower_bound(all(x),v)-x.begin()
#define disc(x) sort(all(x)),x.resize(unique(all(x))-x.begin())
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> li;
#define maxn 500005
struct node{
int s,e,m,lz;ii v;
node *l,*r;
node(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1,lz=0;v={1,s};
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void ppo(){
v.se+=lz;
if(s!=e)l->lz+=lz,r->lz+=lz;
lz=0;
}
void add(int x,int y,int nv){
if(s==x&&e==y){lz+=nv;return;}
if(y<=m)l->add(x,y,nv);
else if(x>m)r->add(x,y,nv);
else l->add(x,m,nv),r->add(m+1,y,nv);
l->ppo(),r->ppo();
v=min(l->v,r->v);
}
inline void flip(int x){
if(s==x&&e==x){v.fi=1-v.fi;return;}
if(x<=m)l->flip(x);
else r->flip(x);
l->ppo(),r->ppo();
v=min(l->v,r->v);
}
ii qry(int x,int y){
ppo();
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
else if(x>m)return r->qry(x,y);
else return min(l->qry(x,m),r->qry(m+1,y));
}
}*rt;
int n,a[maxn],l[maxn],r[maxn];
vector<ii> cyc[maxn],stuff;
int main(){
sf("%d",&n);
for(int i=0;i<n;++i)sf("%d",&a[i]);
l[0]=(a[0]==-1)?0:-1;
for(int i=1;i<n;++i){
if(a[i]==-1)l[i]=i;
else l[i]=l[i-1];
}
r[n-1]=n;
for(int i=n-2;i>=0;--i){
if(a[i]==-1)r[i]=i;
else r[i]=r[i+1];
}
for(int i=0;i<n;++i){
if(a[i]>0){
int d=(r[i]==n?INF:r[i])-i;
if(l[i]!=-1)d=min(d,i-l[i]);
cyc[r[i]].pb({d,i});
}
}
rt=new node(0,n-1);
for(int i=0;i<=n;++i){
if(cyc[i].empty())continue;
sort(all(cyc[i]));
int x=cyc[i].back().se;
--a[x];
//need to reach here at x time
rt->flip(x);
//pf("walk: %d\n",x);
}
for(int i=0;i<n;++i){
if(a[i]>0){
int d=INF;
if(l[i]!=-1)d=min(d,i-l[i]);
d=min(d,(r[i]==n?INF:r[i])-i);
stuff.pb({d,i});
}
}
sort(all(stuff));
for(auto[d,i]:stuff){
int num=a[i];
ii mn=rt->qry(i,n-1);
if(mn.fi!=1)min(a[i],mn.se/(2*d));
int rem=rt->qry(i,i).se;
int cur=rem/(2*d);
if(rem%(2*d)>=d)++cur;
num=min(num,cur);
//pf("take %d of %d\n",num,i);
a[i]-=num;
if(num>0){
rt->flip(i);
rt->add(i,n-1,-num*d*2);
}
}
ll ans=0;
for(int i=0;i<n;++i){
if(a[i]>0)ans+=a[i];
}
pf("%lld\n",ans);
}
/*
5
-1 1 1 1 1
8
-1 1 0 0 -1 0 0 3
8
2 -1 2 -1 2 -1 2 -1
*/
Compilation message
tortoise.cpp: In function 'int main()':
tortoise.cpp:61:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | sf("%d",&n);
| ^
tortoise.cpp:62:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | for(int i=0;i<n;++i)sf("%d",&a[i]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
